---

BFS模板

状态标记为四元组(x,y,key,t)，二进制表示得到的钥匙

注意：

== 的运算优先级比 & 高

一个位置可以有多把钥匙，而且钥匙可以在对应的门里面。

所以要先判断门可不可以进，在判断可不可以得到新钥匙。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const int N = 1e6 + 5;int n,m,k,a,b,c,d;struct Node{    int x,y;    int key;    int t;    Node(){}    Node(int a,int b,int c,int d): x(a), y(b), key(c), t(d) {}};int kx[6],ky[6];bool vis[N];int dirx[] = {0,1,0,-1};int diry[] = {1,0,-1,0};void init(){    memset(vis, 0, sizeof(vis));}char mp[105][105];int getStatus(int x, int y, int key){    return x*10000+y*100+key;}int getkey(int x, int y){    int key = 0;    for(int i = 0; i < k; i++)    {        if(x == kx[i] && y == ky[i])        {            key |= 1 << i;        }    }    return key;}int bfs(){    queue
         
           Q; int st = getStatus(a,b,0); vis[st] = 1; Q.push(Node(a,b,0,0)); while(!Q.empty()) { Node node = Q.front(); Q.pop(); int x = node.x, y = node.y, key = node.key, t = node.t; if(x == c && y == d) return t; for(int i = 0; i < 4; i++) { int nx = x + dirx[i], ny = y + diry[i], nt = t + 1, nkey = key; if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; if(mp[nx][ny] == '#') continue; if(isupper(mp[nx][ny])) { int p = mp[nx][ny] - 'A'; if((nkey & (1<
          
            0) { nkey |= p; } int st = getStatus(nx,ny,nkey); if(vis[st]) continue; vis[st] = 1; Q.push(Node(nx,ny,nkey,nt)); } } return -1;}int main(){ scanf("%d%d%d%d%d%d%d", &n,&m,&k,&a,&b,&c,&d); getchar(); for(int i = 0; i < n; i++) gets(mp[i]); for(int i = 0; i < k; i++) { scanf("%d%d", &kx[i], &ky[i]); } init(); int t = bfs(); printf("%d\n", t); return 0;}