#include<stdio.h> #include<math.h> #include<iostream> using namespace std; #define Max 9 struct Node { int x,y; char c; bool flag; } map[Max][Max],st,en; int f[4][2]= {0,1,0,-1,1,0,-1,0}; int n,m,t; //int step; int myfabs(int x) { if(x<0)x=-x; return x; } int Dfs(int x,int y,int step) { if(x==en.x&&y==en.y&&step==t) return 1; if(myfabs(x-en.x)+myfabs(y-en.y)+step>t) return 0; if((myfabs(x-en.x)+myfabs(y-en.y)+t-step)%2)//剪枝 return 0; map[x][y].flag=false; for(int i=0; i<4; i++) { int u=x+f[i][0]; int v=y+f[i][1]; if(u>=0&&u<n&&v>=0&&v<m&&map[u][v].c!='X'&&map[u][v].flag) { //map[u][v].flag=false; if(Dfs(u,v,step+1)) return 1; //map[u][v].flag=true; } } map[x][y].flag=true; return 0; } int main() { int i,j; //while(scanf("%d%d%d",&n,&m,&t)!=EOF) while(cin>>n>>m>>t) { if(n==0&&m==0&&t==0)break; //getchar(); for(i=0; i<n; i++) { for(j=0; j<m; j++) { //scanf("%c",&map[i][j].c); cin>>map[i][j].c; map[i][j].flag=true; if(map[i][j].c=='S') { st.x=i; st.y=j; } else if(map[i][j].c=='D') { en.x=i; en.y=j; } } //getchar(); } //step=0; //map[st.x][st.y].flag=false; if(Dfs(st.x,st.y,0))printf("YES "); else printf("NO "); } return 0; }
@@@@@@@@@@@@@@@@@@@@@@