Problem Description
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
Source
第46行，if((t2.key&(1<<j))==0){//写成 t2.key&(1<<j)==0竟然一直错，&#%**&*！@#@#@！@！
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #include<stdlib.h> 6 #include<algorithm> 7 using namespace std; 8 #define N 26 9 #define M (1<<10)+6 10 int n,m,t; 11 char mp[N][N]; 12 struct Node{ 13 int x,y; 14 int t; 15 int key; 16 }st,ed; 17 int dirx[]={0,0,-1,1}; 18 int diry[]={-1,1,0,0}; 19 char keys[]={'a','b','c','d','e','f','g','h','i','j'}; 20 char door[]={'A','B','C','D','E','F','G','H','I','J'}; 21 int vis[N][N][M]; 22 void bfs(){ 23 queue<Node>q; 24 q.push(st); 25 vis[st.x][st.y][st.key]=1; 26 Node t1,t2; 27 while(!q.empty()){ 28 t1=q.front(); 29 //printf("*** %d%d %d ",t1.x,t1.y,t1.key); 30 q.pop(); 31 if(t1.x==ed.x && t1.y==ed.y && t1.t<t){ 32 printf("%d ",t1.t); 33 return; 34 } 35 for(int i=0;i<4;i++){ 36 t2=t1; 37 t2.x=t1.x+dirx[i]; 38 t2.y=t1.y+diry[i]; 39 if(mp[t2.x][t2.y]=='*') continue; 40 if(t2.x<0 || t2.x>=n || t2.y<0 || t2.y>=m) continue; 41 if(vis[t2.x][t2.y][t2.key]) continue; 42 if(islower(mp[t2.x][t2.y])){ 43 for(int j=0;j<10;j++){ 44 if(mp[t2.x][t2.y]==keys[j]){ 45 46 if((t2.key&(1<<j))==0){//写成 t2.key&(1<<j)==0竟然一直错，&#%**&*！@#@#@！@！ 47 t2.key+=(1<<j); 48 t2.t++; 49 vis[t2.x][t2.y][t2.key]=1; 50 q.push(t2); 51 } 52 else{ 53 //printf("+++%d ",t2.key); 54 if(vis[t2.x][t2.y][t2.key]==0){ 55 t2.t++; 56 vis[t2.x][t2.y][t2.key]=1; 57 q.push(t2); 58 } 59 } 60 } 61 } 62 } 63 else if(isupper(mp[t2.x][t2.y])){ 64 for(int j=0;j<10;j++){ 65 if(mp[t2.x][t2.y]==door[j]){ 66 if(t2.key&(1<<j)){ 67 t2.t++; 68 vis[t2.x][t2.y][t2.key]=1; 69 q.push(t2); 70 } 71 } 72 } 73 } 74 else{ 75 t2.t++; 76 vis[t2.x][t2.y][t2.key]=1; 77 q.push(t2); 78 } 79 80 81 } 82 } 83 printf("-1 "); 84 } 85 int main() 86 { 87 while(scanf("%d%d%d",&n,&m,&t)==3){ 88 for(int i=0;i<n;i++){ 89 scanf("%s",mp[i]); 90 for(int j=0;j<m;j++){ 91 if(mp[i][j]=='@'){ 92 st.x=i; 93 st.y=j; 94 st.t=0; 95 st.key=0; 96 } 97 if(mp[i][j]=='^'){ 98 ed.x=i; 99 ed.y=j; 100 } 101 } 102 } 103 104 memset(vis,0,sizeof(vis)); 105 bfs(); 106 } 107 return 0; 108 }