随笔-65  评论-6  文章-0  trackbacks-0
 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&&times<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)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理