Problem Description
Ignatius再次被魔王抓走了(搞不懂他咋这么讨魔王喜欢)……
这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，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
每组测试数据之间有一个空行。
. 代表路 * 代表墙 @ 代表Ignatius的起始位置 ^ 代表地牢的出口 A-J 代表带锁的门,对应的钥匙分别为a-j a-j 代表钥匙，对应的门分别为A-J
每组测试数据之间有一个空行。
Output
针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。
Sample Input
4 5 17
@A.B.
a*.*.
*..*^
c..b*
@A.B.
a*.*.
*..*^
c..b*
4 5 16
@A.B.
a*.*.
*..*^
c..b*
Sample Output
16
-1
-1
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std; const int dir[][] = {,,,-,,,-,};
int n, m, t;
char map[][]; struct node
{
int x, y, key; //key的每一个二进制位代表一种钥匙
int step;
bool out(void)
{
if(map[x][y] == '^')
{
return true;
}
return false;
}
bool check(void)
{
if(x>= && x<n && y>= && y<m)
{
if(map[x][y] != '*')
{
return true;
}
}
return false;
}
bool is_key(void)
{
if(map[x][y]>='a' && map[x][y]<='j')
{
return true;
}
return false;
}
bool is_door(void)
{
if(map[x][y]>='A' && map[x][y]<='J')
{
return true;
}
return false;
}
}u,v; //标记已搜索过的状态，根据主角手中拿到的不同的钥匙及其所在位置来区分不同的状态，
//就像推箱子中，用所达某一位置时人物面对的方向来标记某一个状态
int mark[][][]; //数组太大不能在函数中定义
int BFS(void)
{
memset(mark,,sizeof(mark));
queue<node>que;
que.push(u); while(!que.empty())
{
u = que.front();
que.pop(); if(u.out()) //逃出
{
return (t - u.step);
}
for(int i=; i<; i++) //枚举方向
{
v.x = u.x + dir[i][];
v.y = u.y + dir[i][];
v.step = u.step - ;
v.key = u.key; if(v.step == ) //逃不出
{
continue;
} if(v.check() && !mark[v.x][v.y][v.key]) //检查越界，撞墙，标记重复
{
if(v.is_key()) //走到钥匙
{
v.key |= << (map[v.x][v.y] - 'a'); //把钥匙带走，对应二进制标志位置1
}
else if(v.is_door()) //走到门
{
if((v.key & ( << (map[v.x][v.y] - 'A'))) == ) //身上的钥匙不能开这个门
{
continue;
}
}
mark[v.x][v.y][v.key] = ;
que.push(v);
}
}
}
return -;
} int main()
{
while(~scanf("%d%d%d", &n,&m,&t))
{
for(int i=; i<n; i++)
{
scanf("%s", map[i]);
for(int j=; j<m; j++)
{
if(map[i][j] == '@')
{
u.x = i;
u.y = j;
u.key = ;
u.step = t;
}
}
}
printf("%d\n",BFS());
}
return ;
}