广度优先搜索中的状态表示——钥匙型迷宫问题

广度优先搜索中的状态表示——钥匙型迷宫问题

钥匙型迷宫

顾名思义，钥匙型迷宫就是在普通的迷宫问题上，加入钥匙的限制，并在此基础上引申些其他概念，如钥匙能够开门。使得门所在的格子变为可通行的。
如果只要拿到任意一个把钥匙即可，我们可以巧妙地用多起点bfs来解决。
那么在钥匙数量更多、钥匙有多种类型地情况我们应该如何对问题建模，钥匙作为一种状态应当如何保存呢？
首先我们先注意到，在钥匙型迷宫问题中，不同的钥匙是需要保存的，即[位置，钥匙状态]是普通钥匙型迷宫问题中的常见模式。
那么如果有k把不同的钥匙，我们该如何高效地记录呢？一种最普遍的方式就是用一个int类型的数字，在二进制上标记现在持有钥匙的状态。
若k=8，那么初始状态为 ( 00000000 ) 2 (00000000)_2 (00000000)2​，在拿到第一把钥匙后，此状态变为 ( 00000001 ) 2 (00000001)_2 (00000001)2​，以此类推。
同时，我们在记录当前状态是否被访问过时，所开辟的数组int vis[N][M][1<<k]也需要将此状态一同记录。

与普通的迷宫问题类似，蒜头君希望能带着公主早日凯旋。在蒜头君出发之前，你还需要为蒜头君计算出他最快救出公主的时间。
地图用一个 R times CR×C 的字符矩阵来表示。字符 SS 表示蒜头君所在的位置，字符 EE 表示公主所在的位置，字符 # 表示不能踏入的禁区，字符 $ 表示传送门，字符 . 表示该位置安全，数字字符 00 至 44 表示了宝石的类型。蒜头君每次可以从当前的位置走到他上下左右四个方向上的任意一个位置，但不能走出地图边界。蒜头君每走一步需要花费 11 个单位时间，从一个传送门到达另一个传送门不需要花费时间。当蒜头君走到宝石所在的位置时，就视为得到了该宝石，不需要花费额外时间。在此基础上，只有当蒜头君拥有不少于 KK 个宝石时到达字符 EE 所在位置，才能顺利地救出公主。
输入格式
第一行为三个整数，从左到右分别是 R,C,K。
然后是一个R×C 的字符矩阵。字符含义如上所示。

这里面的vis数组表示当前的距离，如果还没走过之前初始化为-1，免去了还需要判断当前位置是否走过的数组判断。
先判断当前位置不能超过限制。
我们通过一个二进制位运算来表示当前钥匙的状态，也就是第一个钥匙有为1，如果第二个钥匙有就是+2，如果第三个钥匙有就+4，如果第四个要是有就+8，以此类推，如果当前的位置在有这么多钥匙的情况有被访问过，那么就跳过去,|=可以理解为如果当前位置或新的钥匙有任何一个有这种钥匙，那么就算有。
我们这时已经排除了走到地图外，走到墙上，走到宝石位置的情况，那么还剩下走到传送门，结束位置和普通位置。
如果当前走到了终点E，并不意味着蒜头君就一定能救出公主，首先需要满足当前位置至少拥有K个宝石，由于我们需要满足二进制表示拥有钥匙的情况，我们需要有一个辅助函数计算其来计算status在二进制下有多少个1。
这个函数的本质就是

int popcount(int x){int ret=0;while(x){ret+=x%2;x/=2;}return ret;
}

写成位运算就是

int popcount(int x){int ret=0;while(x){ret+=x&1;x>>=1;}return ret;
}

如果当前位置是传送门，那么就将所有传送门都访问（所有传送门都不可能是宝石）最后，再把各种普通情况放入队列

#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 205;
int vis[N][N][1 << 5];
string s[N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
struct Node{int x, y, status;Node(){}Node(int _x, int _y, int _status){x = _x; y = _y; status = _status;}
};
queue<Node> q;
int popcount(int x){int ret=0;while(x){ret+=x&1;x>>=1;}return ret;
}
int main()
{int n, m, k;cin >> n >> m >> k;for(int i = 0; i < n; i++) {cin >> s[i];}Node st(0, 0, 0);vector<pair<int, int> > wrap;for(int i = 0; i < n; i++) {for(int j = 0; j < m; j++) {if(s[i][j] == 'S') {st.x = i;st.y = j;} else if (s[i][j] == '$'){wrap.push_back(make_pair(i, j));}}}memset(vis, -1, sizeof(vis));while(!q.empty()) q.pop();q.push(st);vis[st.x][st.y][st.status] = 0;int ans = -1;while(!q.empty() && ans == -1){Node u = q.front(); q.pop();int c = vis[u.x][u.y][u.status];for(int i = 0; i < 4; i++){Node v=u;v.x+=dx[i];v.y+=dy[i];if(v.x<0 || v.x>=n || v.y<0 || v.y>=m || s[v.x][v.y]=='#')continue;if('0'<=s[v.x][v.y] && s[v.x][v.y]<='4')v.status|=1<<(s[v.x][v.y]-'0');if(vis[v.x][v.y][v.status]!=-1)continue;if(s[v.x][v.y]=='E' && popcount(v.status)>=k){ans=c+1;break;}if(s[v.x][v.y]=='$'){for(int k=0;k<wrap.size();k++){if(vis[wrap[k].first][wrap[k].second][v.status]==-1){vis[wrap[k].first][wrap[k].second][v.status]=c+1;q.push(Node(wrap[k].first,wrap[k].second,v.status));}}}else{vis[v.x][v.y][v.status]=c+1;q.push(v);}}}if(ans == -1) cout << "oop!" << endl;else cout << ans << endl;return 0;
}

我们来缕一下这道难题的思路（广度优先搜索部分）：
先把初始位置都设为-1，只要发现位置是-1就说明还没被访问，其他的即为当前位置的距离。
然后枚举下一个位置的四种可能：
首先，先判断有没有越界，不能越界。
其次，如果当前这位是宝石的话，就用二进制表示宝石，如第1个宝石为1，第2个宝石为2，第3个宝石是 2 2 2^2 22以此类推，先计算出当前位置的宝石情况。
再判断如果当前位置是终点，还要判断当前位置的宝石数量够不够，如果够就是答案了。
如果当前这位是传送门，那么就分别传送到其他传送门。
最后判断普通情况，直接放入队列即可。