传送门：
http://acm.hdu.edu.cn/showproblem.php?pid=1429
胜利大逃亡(续)
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 10648 Accepted Submission(s): 3860
这次魔王汲取了上次的教训，把Ignatius关在一个n*m的地牢里，并在地牢的某些地方安装了带锁的门，钥匙藏在地牢另外的某些地方。刚开始Ignatius被关在(sx,sy)的位置，离开地牢的门在(ex,ey)的位置。Ignatius每分钟只能从一个坐标走到相邻四个坐标中的其中一个。魔王每t分钟回地牢视察一次，若发现Ignatius不在原位置便把他拎回去。经过若干次的尝试，Ignatius已画出整个地牢的地图。现在请你帮他计算能否再次成功逃亡。只要在魔王下次视察之前走到出口就算离开地牢，如果魔王回来的时候刚好走到出口或还未到出口都算逃亡失败。
. 代表路
* 代表墙
@ 代表Ignatius的起始位置
^ 代表地牢的出口
A-J 代表带锁的门,对应的钥匙分别为a-j
a-j 代表钥匙，对应的门分别为A-J
每组测试数据之间有一个空行。
@A.B.
a*.*.
*..*^
c..b*
4 5 16
@A.B.
a*.*.
*..*^
c..b*
-1
对于a-j 10把钥匙，我们共有1024种可能
因此，我们可以采用二进制来记录钥匙的集合
//返回新的钥匙集合
//参数：原始的钥匙集合 获得的钥匙的编号
inline int get_key(int key,int num) {
return key | ( << num);
} //返回是否存在门的钥匙
//参数：钥匙集合 门的编号
inline bool has_key(int key,int num) {
return (key & ( << num)) > ;
}
所以一共有3层： dis[max_v][max_v][1024]
有这么多种状态，仔细想想就是站在不同的点拥有不同钥匙集合的状态
注意遇到小写字母的时候记得进行左移 再与前一个状态值进行或运算，例如，假设已经用了A 门的要是，状态此时因该是0000000001，意思是拥有了a，如果下一次遇到了J门的钥
匙，也就是j，那就应该是(1<<10) | (0000000001),那么此时的状态应该是1000000001，当遇到已经拥有钥匙的门的时候再进行右移运算，例如下一次遇到J门时，我们应该先将
1000000001右移10位再与 1进行（&）与运算，如果拥有J门的钥匙 应该是1&1=1 ，是真值，可以通过，如果没有，则0&1=0，是假值，则无法通过。
其余的跟普通的bfs都是一样的
需要注意的地方：
1.越界直接返回
2.遇到了某个钥匙，要生成新的钥匙集合
3.遇到了门，要检查当前钥匙集合能不能打开次门，不能打开就往另外一个方向搜
4.门能打开的话且这种状态没有搜过的话，步数加一
5.如果满足了上面条件，但是超时了，也要重新搜
还有一共很重要的一点
就是搜到了终点的时候，这个返回某值然后结束函数的代码的位置
原来一直都是放在循环的开头，但这个题目不行，wa了几次，也不知道怎么改
我想应该是因为状态的特殊性，毕竟路上有门！
ps：第一个状态压缩的题，纪念一下
具体请参考代码
ac代码：
#include<bits/stdc++.h>
using namespace std;
#define max_v 25
char G[max_v][max_v];//图
int dis[max_v][max_v][];//步数
int dir[][]= {{-,},{,-},{,},{,}}; //方向数组
int n,m,t;//行，列，限定时间
int sx,sy,fx,fy;//起点和终
struct node
{
int x,y;
int key;
node(int a,int b,int c)
{
x=a;
y=b;
key=c;
}
}; inline int get_key(int key,int num)//返回新的钥匙集合
{
//参数：元素的钥匙集合 活动钥匙的编号
return key|(<<num);
} inline bool has_key(int key,int num)//返回是否存在门的钥匙
{
//参数：钥匙集合 门的编号
return (key&(<<num))>;
}
int bfs()
{
//初始化
queue<node> q;
int step=-;
memset(dis,-,sizeof(dis)); q.push(node(sx,sy,));
dis[sx][sy][]=; while(!q.empty())
{
int x=q.front().x;
int y=q.front().y;
int key=q.front().key;
q.pop(); for(int i=; i<; i++)
{
int xx=x+dir[i][];
int yy=y+dir[i][];
int kk=key; if(xx<||xx>=n||yy<||yy>=m||G[xx][yy]=='*')//越界和墙
continue;
if(G[xx][yy]>='a'&&G[xx][yy]<='j')//遇到了钥匙
{
kk=get_key(kk,G[xx][yy]-'a');//返回新的钥匙集合
}
if(G[xx][yy]>='A'&&G[xx][yy]<='J')//遇到了门
{
if(!has_key(kk,G[xx][yy]-'A'))//没有对应的钥匙
{
continue;
}
}
if(dis[xx][yy][kk]==-)
{
dis[xx][yy][kk]=dis[x][y][key]+;//步数加1
if(dis[xx][yy][kk]>=t)//超过了限度时间
{
continue;
}
if(xx == fx && yy == fy)//放这里是因为路上有门的特殊性
{
step = dis[xx][yy][kk];
continue;
} q.push(node(xx,yy,kk));
}
}
}
return step;
}
int main()
{
while(~scanf("%d %d %d",&n,&m,&t))
{
for(int i=; i<n; i++)
{
for(int j=; j<m; j++)
{
scanf("\n%c",&G[i][j]);
if(G[i][j]=='@')
{
sx=i;//起点
sy=j;
}
if(G[i][j]=='^')
{
fx=i;//终点
fy=j;
}
}
}
cout<<bfs()<<endl;
}
return ;
}