HDU 1010 Tempter of the Bone（dfs）

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std; 
 5   
 6 int n,m,t,x1,y3,x2,y2,flag,wall; 
 7 char Map[10][10]; 
 8 int vis[10][10]; 
 9 int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; //四个方向 
10 void dfs(int x,int y,int step) 
11 { 
12     if(flag) return; 
13     if(x==x2&&y==y2&&step==t) //找到就返回 
14     { 
15         flag=1; 
16         return; 
17     } 
18     int re=t-step-abs(x2-x)-abs(y2-y); //剪枝 
19     if(re<0||re&1) return; 
20     for(int i=0;i<4;i++) 
21     { 
22         int xx=x+dir[i][0]; 
23         int yy=y+dir[i][1]; 
24         if(xx<0||xx>=n||yy<0||yy>=m) //出边界不往下搜 
25             continue; 
26         if(Map[xx][yy]!=‘X‘&&vis[xx][yy]==0)  
27         { 
28             vis[xx][yy]=1; 
29             dfs(xx,yy,step+1); 
30             if(flag) return; 
31             vis[xx][yy]=0; //回溯 
32         } 
33     } 
34     return; 
35 } 
36   
37 int main() 
38 { 
39     while(scanf("%d%d%d",&n,&m,&t)!=EOF&&(n&&m&&t)) 
40     { 
41         wall=0,flag=0; 
42         memset(vis,0,sizeof(vis)); 
43         for(int i=0;i<n;i++) 
44             scanf("%s",Map[i]); 
45         for(int i=0;i<n;i++) 
46         { 
47             for(int j=0;j<m;j++) 
48             { 
49                 if(Map[i][j]==‘S‘) x1=i,y3=j; 
50                 if(Map[i][j]==‘D‘) x2=i,y2=j; 
51                 if(Map[i][j]==‘X‘) wall++; 
52             } 
53         } 
54         if(t>n*m-wall-1) //剪枝，如果剩下的路加起来都比时间要小，那肯定不能在规定时间正好走到 
55         { 
56             printf("NO\n"); 
57             continue; 
58         } 
59         vis[x1][y3]=1; 
60         dfs(x1,y3,0); 
61         if(flag==1) 
62             printf("YES\n"); 
63         else
64             printf("NO\n"); 
65     } 
66     return 0; 
67 }