1 #include <cstdio>
2 #include <cstdlib>
3 #include <cmath>
4 #include <cstring>
5 #define MAXSIZE 8
6 char map[MAXSIZE][MAXSIZE];
7 bool continues;
8 int N,M,T;
9 int a1,b1;
10 int a2,b2;
11 int ten[4][2]={
12 0,-1,
13 0,1,
14 1,0,
15 -1,0
16 };
17 inline void trans(int &x,int &y,int times){
18 x+=ten[times][0];
19 y+=ten[times][1];
20 }
21 void dfs(int x,int y,int t){
22 if(!continues||t==T)
23 return;
24 int dis=T-t-(abs(x-a2)+abs(y-b2));
25 if(dis<0||dis&1)
26 return ;
27 int p,q;
28 int times=0;
29 while (continues&×<4){
30 p=x,q=y;
31 trans(p,q,times);
32 times++;
33 if(p<0||p>=N||q<0||q>=M)
34 continue;
35 if(map[p][q]=='D'&&t+1==T){
36 puts("YES");
37 continues=false;
38 return ;
39 }
40 if(map[p][q]=='.'){
41 map[p][q]='X';
42 dfs(p,q,t+1);
43 if(!continues)
44 return ;
45 map[p][q]='.';
46 }
47
48 }
49 }
50 inline void scan(char &ch){
51 while(ch=getchar())
52 if(ch=='.'||ch=='S'||ch=='D'||ch=='X')
53 break;
54 }
55 int main(){
56 //freopen("in.txt","r",stdin);
57 while (scanf("%d %d %d",&N,&M,&T)!=EOF,N||M||T){
58 int i,j,road=0;
59 for(i=0;i<N;i++)
60 for(j=0;j<M;j++){
61 scan(map[i][j]);
62 if(map[i][j]=='.'){
63 road++;
64 continue;
65 }
66 if(map[i][j]=='S')
67 a1=i,b1=j;
68 if(map[i][j]=='D')
69 a2=i,b2=j;
70 }
71 int dis=T-(abs(a1-a2)+abs(b1-b2));
72 if(road+1<T||dis<0||dis&1){
73 puts("NO");
74 continue;
75 }
76 continues=true;
77 dfs(a1,b1,0);
78 if (continues)
79 puts("NO");
80 }
81 return 0;
82 }
83
posted on 2012-05-03 15:06
Leo.W 阅读(151)
评论(0) 编辑 收藏 引用