回溯回溯回溯回溯回溯回溯回溯
hdu1010
#include<stdio.h> #include<string.h> int abs(int x) { return x<0? -1*x:x; } int m,n,T,mp[10][10],Sx,Sy,Dx,Dy,flag,dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; void dfs(int x,int y,int t) { int i,temp; if(x==Dx&&y==Dy&&t==T) {flag=1;return;} if( x<1||x>m||y<1||y>n ) return; temp=T-t-abs(x-Dx)-abs(y-Dy); if( temp<0 || temp%2!=0) return; for(i=0;i<4;i++) { if(x+dir[i][0]>=1&&x+dir[i][0]<=m&&y+dir[i][1]>=1&&y+dir[i][1]<=n) if(mp[x+dir[i][0]][y+dir[i][1]]!='X') { mp[x+dir[i][0]][y+dir[i][1]]='X'; dfs(x+dir[i][0],y+dir[i][1],t+1); if(flag) return; mp[x+dir[i][0]][y+dir[i][1]]='.'; } } } int main() { int i,j,nX; while(scanf("%d%d%d",&m,&n,&T),m+n+T) { getchar(); for(nX=0,i=1;i<=m;i++) { for(j=1;j<=n;j++) { mp[i][j]=getchar(); if(mp[i][j]=='S') Sx=i,Sy=j; else if(mp[i][j]=='D') Dx=i,Dy=j; else if(mp[i][j]=='X') ++nX; } getchar(); } if( m*n-nX-1<T ) { printf("NO\n"); continue; } else { mp[Sx][Sy]='X'; flag=0; dfs(Sx,Sy,0); if(flag) printf("YES\n"); else printf("NO\n"); } } return 0; }