迷宫逃生(计蒜客习题)状态压缩搜索

题目

迷宫逃生（计蒜客习题）

~AC题解
方法： 状压DP+二进制

详解：

⽤⼀个三元bool数组 vis[x][y][mask]表示当前状态，含义是当前在(x, y) 这个点，钥匙状态是 mask;
BFS 搜索，当下⼀个点是钥匙时，新放的状态的 mask 或上这把钥匙，当下⼀个点是⻔时，只有当 mask 上这把钥匙
对应的位是 1 时才能放进新的状态。

附上AC代码~

#include <bits/stdc++.h>
using namespace std;
char maze[30][30];
bool vis[30][30][1024];
int n,m,t,sx,sy,ans=0x3f3f3f3f;
int dir[4][2] = {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
bool in(int x, int y) {
    return 1 <= x && x <= n && 1 <= y && y <= m;
}
struct edge{
	int x,y,ts;
    long long mask;
    //这里的结构体里我没用构造函数，之前用了被坑傻了，查了半天也没差出错，最后改了就好了
    //其实是可以用的
};
int bfs(int sx,int sy){//BFS搜索
	queue<edge> q;
    edge now;
	now.x = sx;
    now.y = sy;
    now.mask = 0;
    now.ts = 0;
    q.push(now);
    vis[sx][sy][0] = 1;
    while(!q.empty()){
		edge now=q.front();
		//cout<<now.x<<" "<<now.y<<"->"<<now.ts<<"<-"<<now.mask<<endl;
        q.pop();
        for(int i=0;i<4;i++){
            int tx = now.x+dir[i][0];
            int ty = now.y+dir[i][1];
            if(in(tx,ty) && maze[tx][ty]!='#'){
            //不在这里对vis进行判断，和一般的BFS不一样，因为我们要判断状态，所以放到下面判断
				if(maze[tx][ty] == '$'){//到了终点，所以不用判断状态
                    if(now.ts+1<t){
                    	ans = min(ans,now.ts+1);
                    }
                }else{
                    if('a'<=maze[tx][ty] && maze[tx][ty]<='j'){//判断是否是钥匙
            			int tmask = now.mask|(maze[tx][ty]-95);//把下一格的钥匙状态转换出
                        if(!vis[tx][ty][tmask]){//判断状态是否重复
                        	edge now2;
                        	now2.x = tx;
                        	now2.y = ty;
                        	now2.ts = now.ts+1;
                        	now2.mask = tmask;
                        	q.push(now2);
                            vis[tx][ty][tmask] = 1;
                        }
                    }else if('A'<=maze[tx][ty] && maze[tx][ty]<='J'){//判断是否是门
                        int tmask = maze[tx][ty]-65;//计算开启门所需的钥匙状态
                       // cout<<tmask<<endl;
                        if((now.mask>>tmask)&1 && !vis[tx][ty][now.mask]){
                        //这里的(now.mask>>tmask)&1是二进制小技巧中判断该位上是否有数的方法
                            edge now2;
                        	now2.x = tx;
                        	now2.y = ty;
                        	now2.ts = now.ts+1;
                        	now2.mask = now.mask;
                        	q.push(now2);
                            vis[tx][ty][now.mask] = 1;
                        }
                    }else{//只是路，无特殊事件
                        if(!vis[tx][ty][now.mask]){
                            edge now2;
                        	now2.x = tx;
                        	now2.y = ty;
                        	now2.ts = now.ts+1;
                        	now2.mask = now.mask;
                        	q.push(now2);
                            vis[tx][ty][now.mask] = 1;
                        }
                    }
                }
            }
		}
    }
    if(ans == 0x3f3f3f3f){
    	return -1;
	}else{
		return ans;
	}
}
int main(){
    freopen("maze.in","r",stdin);
    freopen("maze.out","w",stdout);
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>maze[i][j];
            if(maze[i][j] == '@'){//找到起点
                sx = i;
                sy = j;
            }
        }
    }
	cout<<bfs(sx,sy)<<endl;
    return 0;
}