最短路首先想到bfs,但对于每个位置,拥有不同钥匙的情况下应该视为不同状态,我们在这里采用二进制进行状态压缩,同时采用哈希的思想进行判重。
#include <bits/stdc++.h>
#define f(a,b,c) for(int a=b;a<=c;++a)
#define MAXN 31
using namespace std;
const int dix[5] = {0,1,0,-1,0};
const int diy[5] = {0,0,1,0,-1};
struct Node {
int x,y;
int key;
int step;
};
int n,m,k;
char G[MAXN][MAXN];
queue<Node> q;
unordered_map<int,bool> ha;
unordered_map<char,bool> key;
//对每个点进行hash判重
int hashNode(Node x) {
int ret = 0;
ret += (x.x << 15);
ret += (x.y << 10);
ret += x.key;
return ret;
}
//检查是否为终局状况
bool check(Node x) {
for(char t = 'a'; t <= 'f'; ++t)
if(key[t])
if(!(x.key & (1 << (t - 'a'))))
return false;
return true;
}
int main() {
cin >> n >> m;
//读图
char ch = getchar();
f(i,1,n) {
f(j,1,m) {
ch = getchar();
G[i][j] = ch;
if(ch == '@') {
Node start = {i,j,0,0};
q.push(start);
}
if(ch <= 'f' && ch >= 'a')
key[ch] = true;
}
getchar();
}
while(!q.empty()) {
Node cur = q.front(); q.pop();
//判断是否为重复情况
int hash = hashNode(cur);
if(ha[hash])
continue;
else
ha[hash] = true;
//捡钥匙
char now = G[cur.x][cur.y];
if(now <= 'f' && now >= 'a')
cur.key = (cur.key | (1 << (now - 'a')));
//输出答案
if(check(cur)) {
cout << cur.step << endl;
return 0;
}
//检查有没有钥匙,如果没有就跳过
if(now <= 'F' && now >= 'A')
if(!(cur.key & (1 << (now - 'A'))))
continue;
//这里只检查有没有墙
f(i,1,4) {
int nx = cur.x + dix[i],ny = cur.y + diy[i];
if(nx > 0 && ny > 0 && nx <= n && ny <= m && G[nx][ny] != '#') {
Node nxt = {nx,ny,cur.key,cur.step+1};
q.push(nxt);
}
}
}
//找不到的情况
cout << -1 << endl;
return 0;
}