题目链接：http://hihocoder.com/problemset/problem/1328
这个题bfs到时候不止要存当前的坐标，还要存当前有哪几把钥匙。因为5把钥匙，所以可以直接用位来存，这样也可以解决一个房间里有好几把钥匙的情况。
还有就是走的过程中，一个点重复走多少次的问题，我们用vis(x,y,k)来记录坐标(x,y)的时候拿着钥匙位压后为k的情况，并且初始化成0x7f7f7f，每次更新最短路，假如有重复走并且拥有钥匙情况相同的情况就可以剪掉了。
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f, sizeof(a))
#define lrt rt << 1
#define rrt rt << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<LL, LL> pll;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Node {
int x, y;
int s;
int k;
Node() {}
Node(int xx, int yy, int ss, int kk) : x(xx), y(yy), s(ss), k(kk) {}
}Node;
const int dx[] = {,-,,};
const int dy[] = {,,,-};
const int maxn = ;
int n, m, k;
int sx, sy, ex, ey;
int vis[maxn][maxn][];
char G[maxn][maxn];
char ks[maxn][maxn];
int ret;
queue<Node> q; bool ok(int x, int y) {
return x >= && y >= && x < n && y < m && G[x][y] != '#';
} bool yes(int x, int y, int k) {
if(G[x][y] == '.') return ;
return k & ( << (G[x][y] - 'A'));
} void bfs() {
while(!q.empty()) q.pop();
q.push(Node(sx, sy, , ));
vis[sx][sy][] = ;
while(!q.empty()) {
Node t = q.front(); q.pop();
// printf("%d\n", t.k);
if(t.x == ex && t.y == ey) {
ret = min(ret, t.s);
return;
}
Rep(i, ) {
int x = t.x + dx[i];
int y = t.y + dy[i];
if(ok(x, y)) {
int ck = t.k | ks[x][y];
if(vis[x][y][ck] > t.s + && yes(x, y, ck)) {
vis[x][y][ck] = t.s + ;
q.push(Node(x, y, t.s+, ck));
}
}
}
}
} int main() {
// FRead();
int x, y;
while(~scanf("%d%d%d%d%d%d%d",&n,&m,&k,&sx,&sy,&ex,&ey)) {
Clr(vis, 0x7f7f); Cls(G); Cls(ks); ret = 0x7f7f;
Rep(i, n) Rs(G[i]);
Rep(i, k) {
Rint(x); Rint(y);
ks[x][y] |= ( << i);
}
bfs();
if(ret != 0x7f7f) printf("%d\n", ret);
else printf("-1\n");
}
RT ;
}
这种判断重复的方法是不对的，因为会在一个出不去而不停兜圈子，拿不到钥匙并且会超时。
/*
━━━━━┒ギリギリ♂ eye！
┓┏┓┏┓┃キリキリ♂ mind！
┛┗┛┗┛┃＼○／
┓┏┓┏┓┃ /
┛┗┛┗┛┃ノ)
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┛┗┛┗┛┃
┓┏┓┏┓┃
┃┃┃┃┃┃
┻┻┻┻┻┻
*/
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <climits>
#include <complex>
#include <cassert>
#include <cstdio>
#include <bitset>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <ctime>
#include <set>
#include <map>
#include <cmath>
using namespace std;
#define fr first
#define sc second
#define cl clear
#define BUG puts("here!!!")
#define W(a) while(a--)
#define pb(a) push_back(a)
#define Rint(a) scanf("%d", &a)
#define Rll(a) scanf("%I64d", &a)
#define Rs(a) scanf("%s", a)
#define Cin(a) cin >> a
#define FRead() freopen("in", "r", stdin)
#define FWrite() freopen("out", "w", stdout)
#define Rep(i, len) for(int i = 0; i < (len); i++)
#define For(i, a, len) for(int i = (a); i < (len); i++)
#define Cls(a) memset((a), 0, sizeof(a))
#define Clr(a, x) memset((a), (x), sizeof(a))
#define Full(a) memset((a), 0x7f7f7f, sizeof(a))
#define lrt rt << 1
#define rrt rt << 1 | 1
#define pi 3.14159265359
#define RT return
#define lowbit(x) x & (-x)
#define onenum(x) __builtin_popcount(x)
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef pair<int, int> pii;
typedef pair<string, int> psi;
typedef pair<LL, LL> pll;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef vector<vl> vvl;
typedef vector<bool> vb; typedef struct Node {
int x, y;
int s;
int k;
Node() {}
Node(int xx, int yy, int ss) : x(xx), y(yy), s(ss) { k = ; }
Node(int xx, int yy, int ss, int kk) : x(xx), y(yy), s(ss), k(kk) {}
}Node;
const int dx[] = {,-,,};
const int dy[] = {,,,-};
const int maxn = ;
int n, m, k;
int sx, sy, ex, ey;
char G[maxn][maxn];
char ks[maxn][maxn];
int ret;
queue<Node> q; bool ok(int x, int y) {
return x >= && y >= && x < n && y < m && G[x][y] != '#';
} void bfs() {
while(!q.empty()) q.pop();
q.push(Node(sx, sy, , ));
int wtf = ;
while(!q.empty()) {
if(wtf++ == ) return;
Node t = q.front(); q.pop();
// printf("%d\n", t.k);
if(t.x == ex && t.y == ey) {
ret = min(ret, t.s);
return;
}
Rep(i, ) {
int x = t.x + dx[i];
int y = t.y + dy[i];
if(ok(x, y)) {
int cur = t.k | ks[x][y];
if(G[x][y] == '.' || (cur & ( << (G[x][y] - 'A')))) {
q.push(Node(x, y, t.s+, cur));
}
}
}
}
} int main() {
// FRead();
int x, y;
while(~scanf("%d%d%d%d%d%d%d",&n,&m,&k,&sx,&sy,&ex,&ey)) {
Cls(G); Cls(ks); ret = 0x7f7f7f;
Rep(i, n) Rs(G[i]);
Rep(i, k) {
Rint(x); Rint(y);
ks[x][y] |= ( << i);
}
bfs();
if(ret == 0x7f7f7f) printf("-1\n");
else printf("%d\n", ret);
}
RT ;
}