HDU 1010 Tempter of the Bone(DFS+奇偶剪枝)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目大意：

　　输入 n m t,生成 n*m 矩阵,矩阵元素由 ‘.’ 'S' 'D' 'X' 四类元素组成.

　　S'代表是开始位置； 'D'表示结束位置；'.'表示可以走的路；'X'表示是墙。

　　问:从‘S’ 能否在第 t 步正好走到 'D'.

解题思路：

　　　平常心态做dfs即可，稍微加个奇偶剪枝，第一次做没经验，做过一次下次就知道怎么做了。最后有代码注释解析。

AC Code:

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,t;
 4 int doorX,doorY;
 5 char ca[10][10];
 6 int to[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
 7 int dfs(int x,int y,int cnt)
 8 {
 9     if(x>n||y>m||x<=0||y<=0)return 0;
10     if(cnt==t&&x==doorX&&y==doorY)
11         return 1;
12     int tem=t-cnt-abs(x-doorX)-abs(y-doorY);
13     if(tem<0 || tem&1 )return 0;
14     for(int i=0; i<4; i++)
15     {
16         if(ca[x+to[i][0]][y+to[i][1]]!='X')
17         {
18             ca[x+to[i][0]][y+to[i][1]]='X';
19             if(dfs(x+to[i][0],y+to[i][1],cnt+1))return 1;
20             ca[x+to[i][0]][y+to[i][1]]='.';
21         }
22     }
23     return 0;
24 }
25 int main()
26 {
27     while(scanf("%d%d%d",&n,&m,&t)!=EOF&&n+m+t)
28     {
29         int i,j,wall=0,stratX,stratY;
30         getchar();
31         for(i=1; i<=n; i++)
32         {
33             for(j=1; j<=m; j++)
34             {
35                 scanf("%c",&ca[i][j]);
36                 if(ca[i][j]=='S')
37                     stratX=i,stratY=j;
38                 else if(ca[i][j]=='X')
39                     wall++;
40                 else if(ca[i][j]=='D')
41                     doorX=i,doorY=j;
42             }
43             getchar();
44         }
45         if(n*m-wall<=t)
46         {
47             printf("NO
");
48             continue;
49         }
50         ca[stratX][stratY]='X';
51         if(dfs(stratX,stratY,0))
52             printf("YES
");
53         else
54             printf("NO
");
55     }
56     return 0;
57 }

代码解析：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n,m,t;//n*m 矩阵 和 走的步数 t 
 4 int doorX,doorY;//门的位置
 5 char ca[10][10];//矩阵大小
 6 int to[4][2] = {{0,-1},{0,1},{-1,0},{1,0}};
 7 int dfs(int x,int y,int cnt)
 8 {
 9     if(x>n||y>m||x<=0||y<=0)return 0;//位置越界 
10     if(cnt==t&&x==doorX&&y==doorY)//已走步数 == 要走的步数 t，且位置刚好是门的位置，成功找到一条路
11         return 1;
12     //！ { 奇偶性剪枝：
13     int tem=t-cnt-abs(x-doorX)-abs(y-doorY);
14     if(tem<0 || tem&1 )return 0;
15     // 剩余的步数小于0 || tem 为奇数 都不满足  return 0 即可！}
16 
17     //@{ 遍历八个方向  递归dfs 如果有条件满足 return 1,否则结束 return 0;
18     for(int i=0; i<4; i++)
19     {
20         if(ca[x+to[i][0]][y+to[i][1]]!='X')
21         {
22             ca[x+to[i][0]][y+to[i][1]]='X';
23             if(dfs(x+to[i][0],y+to[i][1],cnt+1))return 1;
24             ca[x+to[i][0]][y+to[i][1]]='.';
25         }
26     }
27     return 0;
28     // @}
29 }
30 int main()
31 {
32     while(scanf("%d%d%d",&n,&m,&t)!=EOF&&n+m+t)
33     {
34         int i,j,wall=0,stratX,stratY;
35         getchar();
36         // 001 { 记录开始位置，墙的个数，以及门的位置
37         for(i=1; i<=n; i++)
38         {
39             for(j=1; j<=m; j++)
40             {
41                 scanf("%c",&ca[i][j]);
42                 if(ca[i][j]=='S')
43                     stratX=i,stratY=j;
44                 else if(ca[i][j]=='X')
45                     wall++;
46                 else if(ca[i][j]=='D')
47                     doorX=i,doorY=j;
48             }
49             getchar();
50         }
51         // 001 }
52         //002 {剪一下枝： 如果墙的个数+走的步数>=矩阵单元的个数，则肯定无法完成此任务，因为还要有开始和门的位置存在
53         if(n*m-wall<=t)
54         {
55             printf("NO
");
56             continue;
57         }
58         //002 }
59         ca[stratX][stratY]='X';//003 { 将开始位置置为墙不可再次访问 }
60 
61         if(dfs(stratX,stratY,0))
62             printf("YES
");
63         else
64             printf("NO
");
65     }
66     return 0;
67 }