作者：jostree 转载请注明出处 http://www.cnblogs.com/jostree/p/4092176.html
使用广度优先搜索，dp[key][x][y]表示在拥有钥匙key并在坐标(x,y)时需要的最少的步数，key的二进制的第i位等于1则代表拥有第i把钥匙。
需要注意以下几点：
1.可能存在同一坐标有多把钥匙。
2.墙和门是在两个坐标间进行移动时的障碍，并不在坐标点上，因此两个方向的移动都要加入wall数组。
2.可以使用方向数组来进行上下左右的搜索。
3.搜索到坐标(n,m)时记录最小步数并退出搜索。
代码如下：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <cstring> 5 #include <queue> 6 #include <limits.h> 7 #include <queue> 8 #define MAXP 11 9 #define MAXN 51 10 using namespace std; 11 int bin[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096}; 12 int dir[4][2]={{-1, 0}, {0, 1}, {1, 0}, {0, -1}};//左，上，右，下 13 int dp[2050][MAXN][MAXN]; 14 int key[MAXN][MAXN]; 15 int wall[MAXN][MAXN][MAXN][MAXN]; 16 int n, m, p; 17 class state 18 { 19 public: 20 int x, y, key, step; 21 }; 22 void solve() 23 { 24 memset(dp, -1, sizeof(dp)); 25 state b; 26 b.x = 1; 27 b.y = 1; 28 b.key = key[1][1]; 29 b.step = 0; 30 queue<state> qu; 31 qu.push(b); 32 int res = INT_MAX; 33 while( qu.size() > 0 ) 34 { 35 state cur = qu.front(); 36 qu.pop(); 37 for( int i = 0 ; i < 4 ; i++ ) 38 { 39 if( cur.x==n && cur.y == m )//到达目的地 40 { 41 res = min(res, cur.step); 42 continue; 43 } 44 state next; 45 next.x = cur.x + dir[i][0]; 46 next.y = cur.y + dir[i][1]; 47 next.key = 0; 48 next.step = 0; 49 //出界 50 if( next.x < 1 || next.x > n ) continue; 51 if( next.y < 1 || next.y > m ) continue; 52 int w = wall[cur.x][cur.y][next.x][next.y]; 53 if( w == 0 ) continue;//是墙 54 if( w > 0 && (cur.key/bin[w]%2 == 0)) continue;//是门没钥匙 55 next.step = cur.step+1; 56 next.key = cur.key | key[next.x][next.y]; 57 if( dp[next.key][next.x][next.y]< 0 ) 58 { 59 dp[next.key][next.x][next.y] = next.step; 60 qu.push(next); 61 } 62 else if(dp[next.key][next.x][next.y] > next.step) 63 { 64 dp[next.key][next.x][next.y] = next.step; 65 qu.push(next); 66 } 67 } 68 } 69 if( res == INT_MAX ) 70 { 71 printf("-1 "); 72 return; 73 } 74 printf("%d ", res); 75 } 76 int main(int argc, char *argv[]) 77 { 78 while(scanf("%d%d%d", &n, &m, &p)!=EOF) 79 { 80 memset(key, 0, sizeof(key)); 81 memset(wall, -1, sizeof(wall)); 82 int tmp; 83 scanf("%d", &tmp); 84 int x1, x2, y1, y2, type; 85 for( int i = 0 ; i < tmp ; i++ ) 86 { 87 scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &type); 88 wall[x1][y1][x2][y2] = type; 89 wall[x2][y2][x1][y1] = type; 90 } 91 scanf("%d", &tmp); 92 for( int i = 0 ; i < tmp ; i++ ) 93 { 94 scanf("%d%d%d", &x1, &x2, &type); 95 key[x1][x2] |= bin[type]; 96 } 97 solve(); 98 } 99 }