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
每组测试数据之间有一个空行。
Output
针对每组测试数据，如果可以成功逃亡，请输出需要多少分钟才能离开，如果不能则输出-1。
Sample Input
4 5 17
@A.B.
a*.*.
..^
c..b*
4 5 16
@A.B.
a*.*.
..^
c..b*
Sample Output
16
-1
分析：
锁和钥匙最多有10把，我们可以用10个二进制数来表示当前的拥有的钥匙状态, 1111111111 每一位0或者1来表示是否有这个钥匙。
如果当前状态下又得到钥匙我们可以用 | 运算符处理得到新状态
如果当前遇到锁，我们可以用 & 运算符来判断是否有这个钥匙
如何遍历所有的状态呢？ 有的状态压缩题目，我们可以用
for(int i=0;i<(1<<10);i++) 这样来遍历所有的情况。
但是这个题目使用bfs，我们知道BFS其实就是遍历所有的位置的可能达到所有状态，所以我们可以用vis[x][y][state] 来表示在当前的位置(x,y)处是否经历过这个状态，如果经历过，我们就可以跳过（因为重复）。这样进行下去直到到终点，并且时间还在t-1之内。
详细的看代码把
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>pii;
#define first fi
#define second se
#define LL long long
#define fread() freopen("in.txt","r",stdin)
#define fwrite() freopen("out.txt","w",stdout)
#define CLOSE() ios_base::sync_with_stdio(false)const int MAXN = 1e5;
const int MAXM = 1e6;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;struct Node{int x,y,state,step;
};
Node S,T;
int n,m,t;
int to[4][2]={
1,0,-1,0,0,1,0,-1};//移动
char mp[50][50];//地图
int vis[50][50][(1<<10)]; //标记
void BFS(){memset(vis,0,sizeof(vis));queue<Node>Q;Q.push(S);Node next;while(!Q.empty()){Node now=Q.front();Q.pop();if(mp[now.x][now.y]=='^') {if(now.step<=t-1){
// 第一个达到这个状态的肯定是步数最小的printf("%d\n",now.step);return ;}}for(int i=0;i<4;i++){int nx,ny;nx=now.x+to[i][0]; ny=now.y+to[i][1];if(mp[nx][ny]=='*') continue;if(nx<0||ny<0||nx>=n||ny>=m) continue;if(mp[nx][ny]>='A'&&mp[nx][ny]<='J') {if((1<<(mp[nx][ny]-'A')) & now.state) {
//判断是否可以打开这个锁next={nx,ny,now.state,now.step+1};if(!vis[nx][ny][next.state]) {vis[nx][ny][next.state]=1;Q.push(next); }}continue;}if(mp[nx][ny]>='a'&&mp[nx][ny]<='j'){next={nx,ny,now.state | (1<<(mp[nx][ny]-'a')),now.step+1};if(!vis[nx][ny][next.state]){vis[nx][ny][next.state]=1;Q.push(next); } continue;}next={nx,ny,now.state,now.step+1};if(!vis[nx][ny][next.state]){vis[nx][ny][next.state]=1;Q.push(next); }}}puts("-1"); // 全部状态都遍历完了但是还没有符合条件的。
}
int main(){CLOSE();
// fread();
// fwrite();while(scanf("%d%d%d",&n,&m,&t)!=EOF){char ch;for(int i=0;i<n;i++){getchar();for(int j=0;j<m;j++){scanf("%c",&mp[i][j]);if(mp[i][j]=='@') S={i,j,0,0};if(mp[i][j]=='^') T={i,j,0,0};}}BFS();}return 0;
}