大体思路：
多维访问标记数组，每一维对应一种拥有钥匙的状态。
不同钥匙状态的搜索 在平行空间 同时进行，互不干扰
这样对一个点的访问动作就有四个属性，x y 为横、纵坐标， s 为钥匙状态， ss为步数。
人生第一道状压搜索~
#include<cstdio> #include<queue> #include<cstring> #include<cmath> #include<iostream> using namespace std; #define rep(i,a,b) for(int i=a; i<=b; i++) #define limit 1005 struct node//记录走到一个点时的状态 { int x, y, s, ss;//x y 坐标， s 拥有钥匙的状态， ss 已走过的步数 node(){} node(int xx, int yy, int sta, int stemp) { x = xx, y = yy, s = sta, ss = stemp ;}//构造函数 }; char Map [limit][limit]; bool Vis [20][limit][limit];/********第一位代表当前拥有钥匙的状态*******/ int N, M; int Dx [4] = {0, 0, 1, -1}; int Dy [4] = {1, -1, 0, 0}; queue<node>Q; void bfs () { while(Q.size() ){ node t = Q.front();//从队列中取点 Q.pop(); for(int i=0; i<4; i++){ int x = t.x + Dx[i], y = t.y + Dy[i];//点的移动 int s = t.s, ss = t.ss;//状态与步数 if(Map[x][y] == '#'){//到达终点 printf("%d\n",t.ss+1); return; } if(Map[x][y] == '*') continue;//碰到墙壁 if(Map[x][y] >= '5' && Map[x][y] <= '8'){//发现钥匙 /*******用一个数的二进制低四位表示钥匙有无的状态*******/ int key = Map[x][y] - '5';//获取钥匙编号 key = pow(2,key);//该钥匙的代表状态 s = s|key;//通过 位或 ，把钥匙加入已有钥匙中 } if(Map[x][y] >= '1' && Map[x][y] <= '4'){//发现门 /*******二进制位检查钥匙有无的状态*******/ int key = Map[x][y] - '1';//获取对应钥匙的编号 key = pow(2,key);//该钥匙的代表状态 if( ! (s & key) ) continue;//通过 位与 判断已有钥匙能不能开这扇门 } if( Vis[s][x][y] ) continue;//该点在当前状态下已访问过 //能进行到这里表示这个点可以走 Vis[s][x][y] = 1;//更新访问标记 Q.push(node(x, y, s, ss+1) );//入队 } } printf("-1\n");//始终没能走到终点，输出-1 } int main () { while( ~scanf("%d%d",&N, &M) ){ memset(Vis, 0, sizeof(Vis));//访问标记全部初始化为假 while(Q.size() ) Q.pop();//清空队列 /*******把Map和它的外边界全部用*填满 这样就不用额外考虑坐标越界的情况了*******/ for(int i=0; i<=N+1; i++) for(int j=0; j<=M+1; j++) Map[i][j] = '*'; for(int i=1; i<=N; i++) for(int j=1; j<=M; j++){ scanf(" %c",&Map[i][j]); if(Map[i][j] == '0') {//发现起点 Q.push( node(i, j, 0, 0) );//将该点入队 Vis[0][i][j] = 1;//更新访问标记 } } bfs();//状压宽搜 } return 0; }
