迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数M和N 后面的M行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。M和N都不超过100, 门不超过10扇。
路径的长度，是一个整数
7
因为会出现需要为了捡钥匙对某个点重复踩多次的情况，所以vis[i][j]无法确认该点是否下次还需要访问，故需要扩充vis状态数组。
用二进制的形式，0101000000，表示已经拥有第二把和第四把钥匙，最多十把钥匙，最多有1024种状态，故vis[i][j][1024]可以确认一个点的访问状态。
相当于每次捡到一把钥匙后，都重置一次vis[i][j]数组，同时不影响其他钥匙状态的vis[i][j]数组
超时:忘记在搜到出口后 立刻结束bfs
#include<iostream> #include<algorithm> #include<queue> #include<math.h> using namespace std; char mp[105][105]; //扩充了vis的状态，解决了需要回头捡钥匙，又要避免bfs重复加入队列的情况 //赋予每个点(i,j)不同的意义，不再是单纯的是否访问过 ，bfs的核心之一 bool vis[105][105][1024]; //vis[i][j][key] key是二进制，表示有无见到某种钥匙，0000100001(33)，表示拥有第1把和第6把钥匙 int toInt(string s) //二进制转为十进制 { int t = 0,ans = 0; for(int i=s.length()-1;i>=0;i--){ ans += (s[i]-‘0‘)*pow(2,t); t++; } return ans; } struct F { int x,y; }f[4]; struct Node { int posi,posj; //该点坐标 int step; //行至该点花费的步数 string key; //该点目前携带的钥匙状态的二进制 }temp; int m,n,minn=100000000; int bgposi,bgposj; //开始点 queue<Node> q; void bfs() { vis[bgposi][bgposj][0] = true; temp.posi = bgposi; temp.posj = bgposj; temp.step = 0; temp.key = "0000000000"; q.push(temp); while(!q.empty()) { temp = q.front(); q.pop(); int i = temp.posi; int j = temp.posj; int step = temp.step; if(mp[i][j] == ‘3‘) { if(step < minn) minn = step; continue; } string key = temp.key; int state = toInt(key); cout<<i<<" "<<j<<" "<<state<<endl; for(int p=0;p<4;p++) { int tempi = i+f[p].x; int tempj = j+f[p].y; if(tempi>=0 && tempi<m && tempj>=0 && tempj<n && vis[tempi][tempj][state]==false && mp[tempi][tempj]!=‘0‘) { vis[tempi][tempj][state] = true; if(mp[tempi][tempj]>=‘A‘ && mp[tempi][tempj]<=‘Z‘ && key[mp[tempi][tempj]-‘A‘] == ‘1‘) { temp.posi = tempi; temp.posj = tempj; temp.step = step+1; q.push(temp); } else if(mp[tempi][tempj]>=‘a‘ && mp[tempi][tempj]<=‘z‘) { temp.posi = tempi; temp.posj = tempj; temp.step = step+1; temp.key[mp[tempi][tempj]-‘a‘] = ‘1‘; q.push(temp); } else if(mp[tempi][tempj] == ‘1‘ || mp[tempi][tempj] == ‘2‘ || mp[tempi][tempj] == ‘3‘) { temp.posi = tempi; temp.posj = tempj; temp.step = step+1; q.push(temp); } } } } } int main() { cin>>m>>n; for(int i=0;i<m;i++) for(int j=0;j<n;j++) { cin>>mp[i][j]; if(mp[i][j] == ‘2‘) { bgposi = i; bgposj = j; } } for(int i=0;i<m;i++) for(int j=0;j<n;j++) for(int k=0;k<1024;k++) vis[i][j][k] = false; f[0].x = -1;f[0].y = 0; f[1].x = 1;f[1].y = 0; f[2].x = 0;f[2].y = -1; f[3].x = 0;f[3].y = 1; bfs(); cout<<minn<<endl; return 0; }
#include<iostream> #include<algorithm> #include<queue> #include<math.h> using namespace std; char mp[105][105]; //扩充了vis的状态，解决了需要回头捡钥匙，又要避免bfs重复加入队列的情况 //赋予每个点(i,j)不同的意义，不再是单纯的是否访问过 ，bfs的核心之一 bool vis[105][105][1024]; //vis[i][j][key] key是二进制，表示有无见到某种钥匙，0000100001(33)，表示拥有第1把和第6把钥匙 int toInt(string s) //二进制转为十进制 { int t = 0,ans = 0; for(int i=s.length()-1;i>=0;i--){ ans += (s[i]-‘0‘)*pow(2,t); t++; } return ans; } struct F { int x,y; }f[4]; struct Node { int posi,posj; //该点坐标 int step; //行至该点花费的步数 string key; //该点目前携带的钥匙状态的二进制 }temp; int m,n; int bgposi,bgposj; //开始点 queue<Node> q; void bfs() { vis[bgposi][bgposj][0] = true; temp.posi = bgposi; temp.posj = bgposj; temp.step = 0; temp.key = "0000000000"; q.push(temp); while(!q.empty()) { temp = q.front(); q.pop(); int i = temp.posi; int j = temp.posj; int step = temp.step; /* 错误：在保证是一步步搜索的情况下 ，bfs保证步数最少，直接退出 if(mp[i][j] == ‘3‘) { if(step < minn) minn = step; continue; }*/ if(mp[i][j] == ‘3‘){ cout<<step; return; } string key = temp.key; int state = toInt(key); //cout<<i<<" "<<j<<" "<<state<<endl; for(int p=0;p<4;p++) { int tempi = i+f[p].x; int tempj = j+f[p].y; if(tempi>=0 && tempi<m && tempj>=0 && tempj<n && vis[tempi][tempj][state]==false && mp[tempi][tempj]!=‘0‘) { vis[tempi][tempj][state] = true; if(mp[tempi][tempj]>=‘A‘ && mp[tempi][tempj]<=‘Z‘ && key[mp[tempi][tempj]-‘A‘] == ‘1‘) { temp.posi = tempi; temp.posj = tempj; temp.step = step+1; q.push(temp); } else if(mp[tempi][tempj]>=‘a‘ && mp[tempi][tempj]<=‘z‘) { temp.posi = tempi; temp.posj = tempj; temp.step = step+1; temp.key[mp[tempi][tempj]-‘a‘] = ‘1‘; q.push(temp); } else if(mp[tempi][tempj] == ‘1‘ || mp[tempi][tempj] == ‘2‘ || mp[tempi][tempj] == ‘3‘) { temp.posi = tempi; temp.posj = tempj; temp.step = step+1; q.push(temp); } } } } } int main() { cin>>m>>n; for(int i=0;i<m;i++) for(int j=0;j<n;j++) { cin>>mp[i][j]; if(mp[i][j] == ‘2‘) { bgposi = i; bgposj = j; } } for(int i=0;i<m;i++) for(int j=0;j<n;j++) for(int k=0;k<1024;k++) vis[i][j][k] = false; f[0].x = -1;f[0].y = 0; f[1].x = 1;f[1].y = 0; f[2].x = 0;f[2].y = -1; f[3].x = 0;f[3].y = 1; bfs(); return 0; }
原文：https://www.cnblogs.com/fzuhyj/p/10691351.html