http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2193
救基友记3
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
话说CZ由于不守基道，被妖怪抓走了，好基友WP在努力讨好高富帅RQ救出CZ的同时，CZ也意识到了自己的错误，然后努力的想逃出妖怪的闺房。
妖怪的闺房是一个n*m的矩阵，并且某些地方安装了带锁的门，钥匙藏在闺房另外的某些地方。刚开始WP被关在(sx,sy)的位置，离开闺房的门在(ex,ey)的位置。WP每分钟只能从一个坐标走到相邻四个坐标中的其中一个。妖怪每t分钟回闺房视察一次，若发现CZ不在原位置便把他再拎回去。经过若干次的尝试，CZ已画出整个闺房的地图。现在请你帮他计算能否再次成功逃亡。只要在妖怪下次视察之前走到出口就算离开闺房，如果妖怪回来的时候刚好走到出口或还未到出口都算逃亡失败。
输入
每组测试数据的第一行有三个整数n,m,t(2<=n,m<=20,t>0)。接下来的n行m列为闺房的地图，其中包括:
. 代表路
* 代表墙
@ 代表CZ的起始位置
^ 代表闺房的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J
. 代表路
* 代表墙
@ 代表CZ的起始位置
^ 代表闺房的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J
每组测试数据之间有一个空行。
输出
针对每组测试数据，如果可以成功逃亡，请输出最少需要多少分钟才能离开，如果不能则输出-1。
示例输入
4 5 17
@A.B.
a*.*.
*..*^
c..b* 4 5 16
@A.B.
a*.*.
*..*^
c..b*
示例输出
16
-1 通过二进制来记录是否已经得到钥匙，例如101010101 说明已经得到a,c,e,g,i钥匙。
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int n,m,tt;
struct node
{
int x,y,z;
int ans;
} q[];
char map[][];
int v[][][];
int jx[]= {,-,,};
int jy[]= {,,,-};
void bfs(int xx,int yy)
{
memset(v,,sizeof(v));
int s=;
int e=;
struct node t,f;
t.x=xx;
t.y=yy;
t.ans=;
t.z=;
q[e++]=t;
v[t.x][t.y][]=;
while(s<e)
{
t=q[s++];
if(map[t.x][t.y]=='^')
{
if(t.ans<tt)
{
printf("%d\n",t.ans);
return ;
}
else
{
printf("-1\n");
return ;
} }
for(int i=; i<; i++)
{
f.x=t.x+jx[i];
f.y=t.y+jy[i];
f.z=t.z;
if(f.x>=&&f.x<n&&f.y>=&&f.y<m&&v[f.x][f.y][f.z]==&&map[f.x][f.y]!='*')//因为钥匙的变化，f.z也会变化，所以有钥匙和没钥匙走的是不同的路线
{
if(map[f.x][f.y]>='a'&&map[f.x][f.y]<='j')
{
int s1,s2,s3;
s1=map[f.x][f.y]-'a';
s2=f.z;
while(s1--)//判断之前有没有拿到过着把钥匙
{
s2=s2/;
}
s3=s2%;
if(s3==)
{
s1=map[f.x][f.y]-'a';
s2=;
while(s1--)
{
s2=s2*;
}
f.z=f.z+s2;
}
f.ans=t.ans+;
q[e++]=f;
v[f.x][f.y][f.z]=;
}
else if(map[f.x][f.y]>='A'&&map[f.x][f.y]<='J')
{
int s1,s2,s3;
s1 = map[f.x][f.y] - 'A';
s2 = f.z;
while(s1--)
{
s2 /= ;
}
s3 = s2 % ;//判断之前有没有拿到钥匙
if(s3 == )
{
f.ans = t.ans + ;
q[e++]=f;
v[f.x][f.y][f.z]=;
}
}
else
{
f.ans=t.ans+;
f.z=t.z;
v[f.x][f.y][f.z]=;
q[e++]=f;
}
}
}
}
printf("-1\n");
}
int main()
{
int x,y,j;
while(scanf("%d%d%d",&n,&m,&tt)!=EOF)
{
for(int i=; i<n; i++)
scanf("%*c%s",map[i]);
for(int i=; i<n; i++)
{
for(j=; j<m; j++)
{
if(map[i][j]=='@')
{
x=i;
y=j;
break;
}
}
if(j!=m) break;
}
bfs(x,y);
}
return ;
}