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模拟的时候到底出了什么问题。我手算的答案和我用算法模拟的过程应该一致，为什么样例输出为16，而我只输出14.
两天之后终于想明白这个题目。。。其实输出14很好模拟，就一个小细节处理问题。。这次又跪在细节上，即在搜索四个方向的时候，每次都要从同一个点出发才行，我居然一个地方手贱把出发点的状态改了。。结果就影响了其余的点，难怪会莫名其妙出来14。细节 啊！！！！！
下面的代码可以出结果。。但是会MLE。。我想剪枝优化，但是失败了。。得用其他方法重新敲一遍！
我想说终于把这道题目A掉了，下午的时候拼命的想怎么剪枝，因为题目必须允许路径往返，因此如果不采取任何措施的话，队列必定会被庞大的但其实毫无用处的点挤爆。
重点在于状态压缩这种算法！！！！！！
所以网上的博客学到了这种状态压缩方法，由我的代码也可以看出来，在结构体里新定义了一个叫做hashnum的变量，用来跟相应的hashkey数组匹配使用，hashkey数组为什么这么定义也是有原因的因为总共有10把钥匙，就意味着任何时候到底手里有几把钥匙有2^10种，为了方便定义数组，就化成十进制，A钥匙代表1，B代表2，C代表4..J代表512；
这样的话，得到任意的钥匙，我都能更新当前状态，通过b.hashnum+=对应字母的hashkey值。。。
求出的b.hashnum主要还是为状态 nodestate服务的，及时更新当前访问了nodestate[x][y][hashnum]=1；下一次再访问到该状态，直接continue。
为什么这个方法对这个题目有效呢
想一下就知道，我的三维数组保存了当前坐标的状态，下一次访问这个点，如果钥匙量（hashnum）没变，即中间走的路完全没用，就滤过它。。。这样就达到了我需要减掉不必要的点。
#include <iostream> #include <cstdio> #include <cstring> #include <queue> using namespace std; int dir[][2]= {{0,1},{0,-1},{1,0},{-1,0}}; char map[30][30]; int hashkey[]={1,2,4,8,16,32,64,128,256,512}; bool nodestate[30][30][1024]; int n,m,t; struct node { short x,y; bool key[11]; short time; int hashnum; }; int bfs(node star) { memset(nodestate,0,sizeof nodestate); queue<node> q; q.push(star); while (!q.empty()) { node b=q.front(); q.pop(); int nx,ny; if (b.time>=t) return -1; if (map[b.x][b.y]=='^') return b.time; for (int i=0; i<4; i++) { nx=b.x+dir[i][0]; ny=b.y+dir[i][1]; if (nx<0||nx>=n||ny<0||ny>=m) continue; if (map[nx][ny]=='*') continue; if (nodestate[nx][ny][b.hashnum]==1) continue;//状态已经被访问过，所以这个点是废点，略过 char ch=map[nx][ny]; if (ch>='A'&&ch<='Z') { int temp=ch-'A'; if (b.key[temp]==false) continue; } if (ch>='a'&&ch<='z') { int temp=ch-'a'; if (!b.key[temp]) { if (!nodestate[nx][ny][b.hashnum+hashkey[temp]])//没有访问的状态，开始增加新点，并记录好该状态已被访问 { node d=b; d.x=nx; d.y=ny; d.time=b.time+1; d.key[temp]=true; d.hashnum+=hashkey[temp]; q.push(d); nodestate[nx][ny][d.hashnum]=1; continue; } } } nodestate[nx][ny][b.hashnum]=1; node c=b; c.x=nx; c.y=ny; c.time=b.time+1; q.push(c); } } return -1; } int main() { int sx,sy; while (scanf("%d%d%d",&n,&m,&t)!=EOF) { for (int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>map[i][j]; if (map[i][j]=='@') { sx=i; sy=j; } } } node start; start.x=sx; start.y=sy; start.hashnum=0; start.time=0; for (int k=0; k<11; k++) { start.key[k]=false; } int ans=bfs(start); printf("%d ",ans); } return 0; }