胜利大逃亡(续) |
| Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) |
| Total Submission(s): 60 Accepted Submission(s): 40 |
| |
|
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 |
思路：BFS，用二进制表示钥匙，那么每一个点用f[i][j][k] 表示是i.j这个点，k的二进制上的1表示拥有哪一把钥匙
总复杂度2^10*20*20
1 /* 2 Author:wuhuajun 3 */ 4 #include <cmath> 5 #include <cstdio> 6 #include <algorithm> 7 #include <cstring> 8 #include <string> 9 #include <cstdlib> 10 #include <queue> 11 using namespace std; 12 13 typedef long long ll; 14 typedef double dd; 15 const int maxn=22; 16 const int dx[]={1,-1,0,0}; 17 const int dy[]={0,0,1,-1}; 18 char s[maxn][maxn],ch; 19 bool f[maxn][maxn][(1<<10)+10]; 20 struct qq 21 { 22 int x,y,v; 23 } ya,pu; 24 queue<qq> q; 25 int step,l,n,m,t,xx,yy,sx,sy,ex,ey,deadline,pos; 26 bool flag; 27 28 29 void close() 30 { 31 exit(0); 32 } 33 bool reach() 34 { 35 if (xx==ex && yy==ey) 36 { 37 if (step<deadline) 38 printf("%d ",step); 39 else 40 printf("-1 "); 41 flag=true; 42 return true; 43 } 44 return false; 45 } 46 47 void print() 48 { 49 for (int i=8;i>=1;i--) 50 printf("%d",pos & (i<<1)); 51 puts(""); 52 } 53 54 void pushin() 55 { 56 pu=ya; 57 pu.x=xx; pu.y=yy; 58 if (t!=0) 59 pu.v=ya.v | (1<<(t-1)); 60 q.push(pu); 61 } 62 63 void judge() 64 { 65 if (!(1<=xx && xx<=n && 1<=yy && yy<=m)) return; 66 ch=s[xx][yy]; 67 if (ch=='*') return;//wall 68 if (ch=='.' || ch=='@') 69 { 70 t=0; 71 if (f[xx][yy][ya.v]) return; 72 f[xx][yy][ya.v]=true; 73 pushin(); 74 return; 75 } 76 if ('a'<=ch && ch<='j') //key 77 { 78 t=ch-'a'+1; 79 pos=ya.v | (1<<(t-1)); 80 if (f[xx][yy][pos]) return;//是否到过(xx,yy)这个点 81 f[xx][yy][pos]=true; 82 pushin(); 83 } 84 else 85 { //door 86 t=ch-'A'+1; 87 if ((ya.v & (1<<(t-1)))==0) return;//在(ya.x,ya.y)点上钥匙不能开门 88 if (f[xx][yy][ya.v]) return; 89 f[xx][yy][ya.v]=true; 90 t=0; 91 pushin(); 92 } 93 } 94 95 void work() 96 { 97 memset(f,false,sizeof(f)); 98 while (!q.empty()) q.pop(); 99 step=0; flag=true; 100 ////////////////// 101 f[sx][sy][0]=true; 102 ya.x=sx; 103 ya.y=sy; 104 ya.v=0; 105 q.push(ya); 106 while (!q.empty()) 107 { 108 step++; 109 //printf("Step:%d ----------------------- ",step-1); 110 l=q.size(); 111 while (l--) 112 { 113 ya=q.front(); 114 q.pop(); 115 // printf("x:%d y:%d v:%d ",ya.x,ya.y,ya.v); 116 for (int i=0;i<4;i++) 117 { 118 xx=dx[i]+ya.x; 119 yy=dy[i]+ya.y; 120 if (reach()) return; 121 judge(); 122 } 123 } 124 } 125 printf("-1 "); 126 } 127 128 129 void init() 130 { 131 while (scanf("%d %d %d",&n,&m,&deadline)!=EOF) 132 { 133 for (int i=1;i<=n;i++) 134 { 135 scanf("%s",s[i]); 136 for (int j=m-1;j>=0;j--) 137 s[i][j+1]=s[i][j]; 138 s[i][0]=' '; 139 } 140 for (int i=1;i<=n;i++) 141 for (int j=1;j<=m;j++) 142 { 143 if (s[i][j]=='@') 144 { 145 sx=i;sy=j; 146 } 147 if (s[i][j]=='^') 148 { 149 ex=i; ey=j; 150 } 151 } 152 work(); 153 } 154 } 155 156 int main () 157 { 158 init(); 159 close(); 160 return 0; 161 }