1 #include <bits/stdc++.h> 2 using namespace std; 3 4 int n,m,aim,x,y,x2,y2,ff,cot,tt,xnum; 5 char a[10][10]; 6 int flag[10][10]; 7 int dir[4][2]= {1,0,0,1,-1,0,0,-1}; 8 9 void dfs(int x,int y) 10 { 11 if(ff) 12 return ; 13 if(cot==aim&&a[x][y]=='D') 14 { 15 ff=1; 16 return ; 17 } 18 if(cot>=aim||a[x][y]=='D') 19 return ; 20 int dis=aim-cot-(abs(x-x2)+abs(y-y2)); 21 if(dis<0||dis%2) 22 return ; 23 for(int i=0; i<4; i++) 24 { 25 int xx=x+dir[i][0]; 26 int yy=y+dir[i][1]; 27 if(xx>=0&&xx<n&&yy>=0&&yy<m&&!flag[xx][yy]&&a[xx][yy]!='X') 28 { 29 flag[xx][yy]=1; 30 cot++; 31 dfs(xx,yy); 32 flag[xx][yy]=0; 33 cot--; 34 } 35 else 36 continue; 37 } 38 } 39 40 int main() 41 { 42 while(scanf("%d%d%d",&n,&m,&aim)&&n&&m&&aim) 43 { 44 memset(flag,0,sizeof(flag)); 45 memset(a,0,sizeof(a)); 46 xnum=ff=cot=0; 47 for(int i=0; i<n; i++) 48 { 49 scanf("%s",a[i]); 50 for(int j=0; j<m; j++) 51 { 52 if(a[i][j]=='S') 53 x=i,y=j; 54 if(a[i][j]=='D') 55 x2=i,y2=j; 56 if(a[i][j]=='X') 57 xnum++; 58 } 59 } 60 if(n*m-xnum>=aim) 61 { 62 flag[x][y]=1; 63 dfs(x,y); 64 } 65 if(ff) 66 printf("YES "); 67 else 68 printf("NO "); 69 } 70 return 0; 71 }
只有不断学习才能进步！