玄关求助!
查看原帖
玄关求助!
1024387
xQWQx楼主2024/7/30 09:45

后两个点RE了QWQ

#include<bits/stdc++.h> 
using namespace std;
struct node{
    int x,y,ans;
    int st;
}; 
int n,m,v;
int dx[4]={0,1,0,-1};//方向
int dy[4]={1,0,-1,0};
bool vis[25][25][(1<<20)];
int maze[25][25][25][25];
int k[105][105][105];//锁
bool in(int x,int y){
    return 1<=x&&x<=n&&1<=y&&y<=m;
}
int BFS(){
    queue<node> Q;
    Q.push((node){1,1,0,0});
    vis[1][1][0]=1;//锁
    while(Q.size()){
        node t=Q.front();
        Q.pop();
        if(t.x==n&&t.y==m){
            cout<<t.ans;
            exit(0);
        }
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i];
            int ny=t.y+dy[i];
            if(in(nx,ny)==0
               ||maze[t.x][t.y][nx][ny]==-1
               ||vis[nx][ny][t.st]==1) continue;//判断

            if((maze[t.x][t.y][nx][ny])!=0){
                if(((1<<(maze[t.x][t.y][nx][ny]-1))&t.st)==0) continue;
            }//有锁无钥匙

            int sum=t.st;
            for(int j=1;j<=k[nx][ny][0];j++){
                sum|=(1<<(k[nx][ny][j]-1));
            }//开锁
            vis[nx][ny][sum]=1;//锁
            Q.push((node){nx,ny,t.ans+1,sum});//入队
        }
    }
    cout<<-1;
}
int main(){
    cin>>n>>m>>v>>v;
    for(int i=1;i<=v;i++){
        int x1,x2,y1,y2,u;
        cin>>x1>>y1>>x2>>y2>>u;
        if(u==0) maze[x1][y1][x2][y2]=maze[x2][y2][x1][y1]=-1;//墙
        else maze[x1][y1][x2][y2]=maze[x2][y2][x1][y1]=u;//锁
    }
    cin>>v;
    for(int i=1;i<=v;i++){
        int x,y,u;
        cin>>x>>y>>u;
        k[x][y][0]++;
        k[x][y][k[x][y][0]]=u;
    }
    BFS();
    return 0;
}
2024/7/30 09:45
加载中...