2335:拯救雅典娜
时间限制:1 秒
内存限制:32 兆
题目描述
悲剧的雅典娜又被坏蛋抓走了!于是乎,正在马尔代夫度假的青铜五小强又要加班了-_-!
这次雅典娜被抓到了一个迷宫中,这个迷宫是方形的,且只有一层,由n*m个完全一样的正方形房间组成。
青铜五小强来到了房间S,也就是他们的起始点,雅典娜被关在房间E。而其他的房间,有些无法进入。小强们只能向前后左右四个方向行进,他们每到达一个新的房间就会消耗1个单位的时间。
已知雅典娜只能坚持t个单位的时间,时间一过立马挂掉,现在给你迷宫的布局、青铜五小强的起始位置S、雅典娜被关的位置E,请你判断小强们是否能够在雅典娜挂掉之前找到她。
注意:我们规定小强们到达起始位置时已经消耗了1个单位的时间了。
输入格式
输入包含多组测试数据。
每组输入的第一行为3个整数n,m,t(0<=n,m<=10,1<=t<=20),t表示雅典娜能够坚持的时间,n和m不会同时为1,当n和m中有一个为0或都为0时,输入结束。
接下来n行,每行输入m个字符,每个字符表示一个房间的情况:
‘.’:表示此房间可以通过。
‘#’:表示此房间不可以通过,需要绕道。
‘S’:表示青铜五小强的其实位置。
‘E’:表示雅典娜被关的位置。
题目保证每组输入有且仅有一个S和E。
输出
对于每组输入,如果能够在雅典娜挂掉之前找到她,输出“Oh Yes!!!”,否则输出“Tragedy!!!”。
样例输入
4 4 10
....
....
....
S##E
3 4 20
.#E.
.S#.
.#..
3 0 5
样例输出
Oh Yes!!!
Tragedy!!!
1 //简单的DFS,注意有搜索深度的限制(t)。 2 #include<stdio.h> 3 #include<string.h> 4 const int di[4]={-1,1,0,0},dj[4]={0,0,-1,1}; 5 int sx,sy,n,m,t,i,j; 6 bool mark[110][110],ans; 7 char map[110][110]; 8 void tr(int T,int pi,int pj) 9 { 10 if(T==t)return; 11 int ti,tj,k; //必须是局部变量!!! 12 for(k=0;k<4;k++){ 13 ti=pi+di[k]; 14 tj=pj+dj[k]; 15 if(!mark[ti][tj]&&(map[ti][tj]=='.'||map[ti][tj]=='E')){ 16 mark[ti][tj]=true; 17 if(map[ti][tj]=='E'){ans=true;return;} 18 else tr(T+1,ti,tj); 19 if(ans==true)return; 20 mark[ti][tj]=false; 21 } 22 23 } 24 } 25 int main() 26 { 27 while(scanf("%d%d%d",&n,&m,&t),n&&m&&t) 28 { 29 memset(map,'\0',sizeof(map)); 30 memset(mark,false,sizeof(mark)); 31 for(i=1;i<=n;i++){ 32 { 33 scanf("%s",map[i]+1); 34 for(j=1;j<=m;j++){ 35 if(map[i][j]=='S'){sx=i;sy=j;} 36 } 37 } 38 } 39 mark[sx][sy]=true; 40 ans=false; 41 tr(1,sx,sy); 42 printf("%s\n",ans?"Oh Yes!!!":"Tragedy!!!"); 43 } 44 return 0; 45 }