给一个n*m的矩阵，从11，走到nm，格子和格子之间可能有墙，也可能有门，有的格子上面有钥匙，相应的钥匙开相应的们，捡钥匙和开门都不需要时间，问你最少多少部能走到nm.
思路：
哎！一眼就看出来了是个状态压缩搜索的水题，结果wa了将近两个小时，就是因为忽略了一个点可能有多把钥匙，回来说下这个题，我们可以开一个数组mark[x][y][key]，表示当前的这个点xy所含有的钥匙状态是key的时候是否走过，key是一个二进制压缩的数，这个很简单不解释，同时在开一个数组bnk[x1][y1][x2][y2]记录从x1y1到点x2y2的中间是什么东西（墙，门，或者什么都没有），然后就是遍历就行了，题目一点不难，还不明白的直接看代码就知道了。
#include<stdio.h> #include<string.h> #include<queue> #define N 20 using namespace std; typedef struct { int x ,y ,t ,key; }NODE; NODE xin ,tou; int mark[N][N][1<<10+1]; int bank[N][N][N][N]; int map[N][N]; int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0}; int BFS(int n ,int m) { memset(mark ,0 ,sizeof(mark)); xin.x = xin.y = 1; xin.t = 0; xin.key = 0 | map[1][1]; mark[xin.x][xin.y][xin.key] = 1; queue<NODE>q; q.push(xin); while(!q.empty()) { tou = q.front(); q.pop(); for(int i = 0 ;i < 4 ;i ++) { xin.x = tou.x + dir[i][0]; xin.y = tou.y + dir[i][1]; xin.t = tou.t + 1; if(xin.x < 1 || xin.x > n || xin.y < 1 || xin.y > m) continue; if(!bank[tou.x][tou.y][xin.x][xin.y]) continue; if(bank[tou.x][tou.y][xin.x][xin.y] == -1 || tou.key & (1 << (bank[tou.x][tou.y][xin.x][xin.y] - 1))) { if(!map[xin.x][xin.y]) xin.key = tou.key; else xin.key = tou.key | map[xin.x][xin.y]; if(!mark[xin.x][xin.y][xin.key]) { mark[xin.x][xin.y][xin.key] = 1; q.push(xin); if(xin.x == n && xin.y == m) return xin.t; } } } } return -1; } int main () { int n ,m ,p ,k ,q ,i; int x1 ,x2 ,y1 ,y2 ,key; while(~scanf("%d %d %d" ,&n ,&m ,&p)) { scanf("%d" ,&k); memset(bank ,255 ,sizeof(bank)); for(i = 1 ;i <= k ;i ++) { scanf("%d %d %d %d %d" ,&x1 ,&y1 ,&x2 ,&y2 ,&key); bank[x1][y1][x2][y2] = bank[x2][y2][x1][y1] = key; } scanf("%d" ,&q); memset(map ,0 ,sizeof(map)); for(i = 1 ;i <= q ;i ++) { scanf("%d %d %d" ,&x1 ,&y1 ,&key); map[x1][y1] |= (1 << (key - 1)); } printf("%d " ,BFS(n ,m)); } return 0; }