胜利大逃亡(续)（HDOJ 1429）
Problem Description
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
Input
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为地牢的地图，其中包括:
. 代表路
- 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J
每组测试数据之间有一个空行。
Output
针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。
Sample Input
4 5 17 @A.B. a*.*. *..*^ c..b* 4 5 16 @A.B. a*.*. *..*^ c..b*
Sample Output
16 -1
My Code
#include
#include
#include
using namespace std;
int t;
int n, m;
int r = 6;
int dx[4] = {0, 1, -1, 0};
int dy[4] = {1, 0, 0, -1};
char map[25][25];
int v[25][25][1 << 10]; //因为拿到钥匙可能还要往回走，所以钥匙状态也要标记
struct node
{
int x, y;
int step;
int key; //当前钥匙获得状态
} s;
bool check(node p)
{
if (p.x < 0 || p.y < 0)
return false;
if (p.x >= n || p.y >= m)
return false;
if (map[p.x][p.y] == '*')
return false;
if (v[p.x][p.y][p.key])
return false;
return true;
}
void bfs()
{
queue q;
q.push(s);
node next, p;
memset(v, 0, sizeof(v));
v[s.x][s.y][s.key] = 1;
while (!q.empty())
{
p = q.front();
q.pop();
if (p.step >= t - 1) //如果时间只剩1分钟了还没到终点，那么就挂了
continue;
for (int i = 0; i < 4; i++)
{
next.x = p.x + dx[i];
next.y = p.y + dy[i];
next.key = p.key; //这个千万不能忘记
//cout << next.x << ' ' << next.y << ' ' << next.key << endl;
if (check(next))
{
next.step = p.step + 1;
if (map[next.x][next.y] >= 'A' && map[next.x][next.y] <= 'J')
{
if ((next.key & (1 << (map[next.x][next.y] - 'A'))) == 0)
continue; //通过按位与来判断是否获得了钥匙
}
if (map[next.x][next.y] >= 'a' && map[next.x][next.y] <= 'j')
next.key |= (1 << (map[next.x][next.y] - 'a')); //按位或更新状态
if (!v[next.x][next.y][next.key])
{
if (map[next.x][next.y] == '^') //到终点了，输出步数，退出
{
cout << next.step << endl;
return;
}
//cout<> n >> m >> t)
{
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
{
cin >> map[i][j];
if (map[i][j] == '@')
{
s.x = i; //起始点初始化
s.y = j;
s.key = 0;
s.step = 0;
}
}
bfs();
}
return 0;
} 
OωO
