题意：一只小狗要刚好在t时刻从起点都到终点，问可不可以。
注意剪枝。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 using namespace std; 5 int maze[9][9]; 6 bool vis[9][9]; 7 int n,m,t; 8 bool ans; 9 struct Point 10 { 11 int x,y; 12 }; 13 int dx[4]={0,0,-1,1}; 14 int dy[4]={1,-1,0,0}; 15 Point p,e; 16 void dfs(Point cur,int dep) 17 { 18 vis[cur.x][cur.y]=true; 19 if(!ans&&cur.x==e.x&&cur.y==e.y&&dep==t) 20 { 21 ans=true; 22 return ; 23 } 24 if(!ans&&dep>t) 25 return ; 26 for(int i=0;i<4;i++) 27 { 28 Point dcur; 29 dcur.x=cur.x+dx[i]; 30 dcur.y=cur.y+dy[i]; 31 if(dcur.x<1||dcur.x>n||dcur.y<1||dcur.y>m) 32 continue; 33 if(vis[dcur.x][dcur.y]) 34 continue; 35 if(!maze[dcur.x][dcur.y]) 36 continue; 37 if(!ans) 38 { 39 dfs(dcur,dep+1); 40 vis[dcur.x][dcur.y]=false;//注意回溯 41 } 42 } 43 } 44 int main() 45 { 46 while(scanf("%d%d%d",&n,&m,&t)) 47 { 48 if(n==0&&m==0&&t==0) 49 break; 50 char s[15]; 51 for(int i=1;i<=n;i++) 52 { 53 scanf("%s",s+1); 54 for(int j=1;j<=m;j++) 55 { 56 if(s[j]=='X') 57 maze[i][j]=0; 58 else if(s[j]=='.') 59 maze[i][j]=1; 60 else if(s[j]=='S') 61 { 62 p.x=i; 63 p.y=j; 64 maze[i][j]=1; 65 } 66 else 67 { 68 e.x=i; 69 e.y=j; 70 maze[i][j]=1; 71 } 72 } 73 } 74 ans=false; 75 memset(vis,false,sizeof(vis)); 76 int a=abs(e.x+e.y-p.x-p.y); 77 if(a>t) //剪枝 78 ans=false; 79 else if(a%2!=t%2) //剪枝 80 ans=false; 81 else 82 dfs(p,0); 83 if(ans) 84 printf("YES "); 85 else 86 printf("NO "); 87 } 88 return 0; 89 }