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,'',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
",ans?"Oh Yes!!!":"Tragedy!!!");
43     }
44     return 0;
45 }