胜利大逃亡(续)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3914 Accepted Submission(s): 1285
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*
4 5 16
@A.B.
a*.*.
*..*^
c..b*
Sample Output
16
-1
这道题是bfs比较难的，如果没有想到好的方法是没有办法顺利完成的，我也是看了网上，大牛们的代码才明白这道题的技巧所在，感觉真的是很神奇的，，，让我初识位压缩的一道BFS题，
现在和大家分享一下：
用二进制来表示手头的钥匙有哪些，100表示有第三把钥匙，111表示有第三、二、一把，搜索下一点时，如果该点为钥匙点，则可采用|运算来
模拟拾取，显然0001 | 1000 = 1001，同理，当为相应的门时采用&运算来模拟开启，例如1101 & 0001 = 0001（即可以打开'A'门）
//hdu1429利用二进制的&和|运算：
#include<iostream>
#include<queue>
using namespace std;
const int T = ;
char g[T][T];
int vis[T][T][],n,m,t,ans;
int dir[][]={{,},{,},{,-},{-,}}; struct point
{
int x;
int y;
int step;
int key;
};
point s; void inset()
{
for(int i=;i<n;i++)
{
cin>>g[i];//输入一行字符
for(int j=;j<m;j++)
{
if(g[i][j]=='@')
{
s.x=i;
s.y=j;
s.key=;
s.step=;
}
}
}
} int cheak(int x,int y)
{
if(s.x>= && s.x<n && s.y>= && s.y<m )//没有越界
return ;
return ;
}
void bfs()
{
queue<point> Q;
point tp;
ans=-;
memset(vis,,sizeof(vis));
vis[s.x][s.y][s.key]=;//可以走回头路但是必须拿到钥匙，改变[s.key]的值，这就是技巧
Q.push(s);
while(!Q.empty())
{
tp=Q.front();
Q.pop();
for(int k=;k<;k++)
{
s=tp;
s.x=tp.x+dir[k][];
s.y=tp.y+dir[k][];
if(cheak(s.x,s.y) && g[s.x][s.y]!='*' && !vis[s.x][s.y][s.key])//注意，这里vis[s.x][s.y][s.key]是0的时候才能进
{
if(g[s.x][s.y]=='.' || g[s.x][s.y]=='@')
{
vis[s.x][s.y][s.key]=;
s.step+=;
Q.push(s);
//cout<<s.x<<" "<<s.y<<endl;
}
if(g[s.x][s.y]=='^')
{
if(s.step+<t)
ans=s.step+;
return ;
}
if(g[s.x][s.y]>='A' && g[s.x][s.y]<='J')
{ //eg:a<<2表示将a是二进制左移2位（相当于*4），这里用来表示钥匙eg:A-A=0;1<<0,就是0000 0001就是第一把钥匙了。
int key=<<(g[s.x][s.y]-'A');//同理当g[s.x][s.y]='B'时，就是1<<2,就是0000 0010,表示第二把钥匙；
if(s.key & key)//按位于运算，当有对应的钥匙时，等式成立；才能打开门
{
vis[s.x][s.y][s.key]=;
s.step+=;
Q.push(s);
//cout<<s.x<<" "<<s.y<<endl;
}
}
if(g[s.x][s.y]>='a' && g[s.x][s.y]<='j')
{
int key=<<(g[s.x][s.y]-'a');
if(!vis[s.x][s.y][s.key|key])//按位或运算，吸收钥匙；
{
vis[s.x][s.y][s.key|key]=;
s.step+=;
s.key=s.key|key;
Q.push(s);
//cout<<s.x<<" "<<s.y<<endl;
}
}
}
}
}
} int main()
{
while(cin>>n>>m>>t)
{
inset();
bfs();
cout<<ans<<endl;
}
return ;
}
/*
4 5 17
@A.B.
a*.*.
*..*^
c..b* 4 5 16
@A.B.
a*.*.
*..*^
c..b* 4 5 17
@A.B.
a*.*D
*..*^
c..b* 4 5 25
@A.B.
a*.*C
*..*^
c..b*
*/ /* 16
-1
-1
20 */
不明之处，已经附上注释，不理解的可以私下交谈，也可以相互学习，积累经验，大家多多支持哈。。。