作者：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)时记录最小步数并退出搜索。
代码如下：
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <queue>
#include <limits.h>
#include <queue>
#define MAXP 11
#define MAXN 51
using namespace std;
int bin[] = {, , , , , , , , , , , , };
int dir[][]={{-, }, {, }, {, }, {, -}};//左，上，右，下
int dp[][MAXN][MAXN];
int key[MAXN][MAXN];
int wall[MAXN][MAXN][MAXN][MAXN];
int n, m, p;
class state
{
public:
int x, y, key, step;
};
void solve()
{
memset(dp, -, sizeof(dp));
state b;
b.x = ;
b.y = ;
b.key = key[][];
b.step = ;
queue<state> qu;
qu.push(b);
int res = INT_MAX;
while( qu.size() > )
{
state cur = qu.front();
qu.pop();
for( int i = ; i < ; i++ )
{
if( cur.x==n && cur.y == m )//到达目的地
{
res = min(res, cur.step);
continue;
}
state next;
next.x = cur.x + dir[i][];
next.y = cur.y + dir[i][];
next.key = ;
next.step = ;
//出界
if( next.x < || next.x > n ) continue;
if( next.y < || next.y > m ) continue;
int w = wall[cur.x][cur.y][next.x][next.y];
if( w == ) continue;//是墙
if( w > && (cur.key/bin[w]% == )) continue;//是门没钥匙
next.step = cur.step+;
next.key = cur.key | key[next.x][next.y];
if( dp[next.key][next.x][next.y]< )
{
dp[next.key][next.x][next.y] = next.step;
qu.push(next);
}
else if(dp[next.key][next.x][next.y] > next.step)
{
dp[next.key][next.x][next.y] = next.step;
qu.push(next);
}
}
}
if( res == INT_MAX )
{
printf("-1\n");
return;
}
printf("%d\n", res);
}
int main(int argc, char *argv[])
{
while(scanf("%d%d%d", &n, &m, &p)!=EOF)
{
memset(key, , sizeof(key));
memset(wall, -, sizeof(wall));
int tmp;
scanf("%d", &tmp);
int x1, x2, y1, y2, type;
for( int i = ; i < tmp ; i++ )
{
scanf("%d%d%d%d%d", &x1, &y1, &x2, &y2, &type);
wall[x1][y1][x2][y2] = type;
wall[x2][y2][x1][y1] = type;
}
scanf("%d", &tmp);
for( int i = ; i < tmp ; i++ )
{
scanf("%d%d%d", &x1, &x2, &type);
key[x1][x2] |= bin[type];
}
solve();
}
}