HDU--1010 Tempter of the Bone（深搜+奇偶剪枝）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1010

我认为的剪枝就是在本来的代码中加入一些附加条件使之不去进行多余的计算，防止超时

AC代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 int n,m,t,k,flag,starex,starey,endx,endy,sum;
 6 char s[10][10];
 7 int book[10][10];
 8 int tx,ty,head,tail;
 9 struct node
10 {
11     int x,y,f;
12 }que[500];
13 int abs(int a)
14 {
15     if(a<0)
16     a=-a;
17     return a;
18 }
19 int dfs(int x,int y,int step)
20 {
21     int tx,ty;
22     int a[4]={1,-1,0,0},b[4]={0,0,1,-1};
23     if(flag==1)
24     return 0;
25     if(t==step&&x==endx&&y==endy)
26     {
27         flag=1;
28         return 0;
29     }
30     int mindis=abs(x-endx)+abs(y-endy);  /*当前点到终点的最短距离*/
31     if(mindis>t-step||(mindis+ t-step)%2!=0)
32     return 0;
33     for(int i=0;i<4;i++)
34     {
35         tx=x+a[i];
36         ty=y+b[i];
37         if(tx>=n||tx<0||ty>=m||ty<0)
38         continue;
39         if((s[tx][ty]=='.'||s[tx][ty]=='D')&&book[tx][ty]==0)
40         {
41             book[tx][ty]=1;
42             dfs(tx,ty,step+1);
43             book[tx][ty]=0;
44         }
45     }
46     return 0;
47 }
48 int main()
49 {
50     while(~scanf("%d%d%d",&n,&m,&t))
51     {
52         sum=0;
53         if(n==0&&m==0&&t==0)
54         break;
55         for(int i=0;i<n;i++)
56         {
57             scanf("%s",s[i]);
58             for(int j=0;j<m;j++)
59             {
60                 if(s[i][j]=='S')
61                 {
62                     starex=i;starey=j;
63                 }
64                 if(s[i][j]=='D')
65                 {
66                     endx=i;endy=j;
67                 }
68                 if(s[i][j]=='X')
69                 {
70                     sum++;
71                 }
72             }
73         }
74         if(n*m-sum-1<t)
75         {
76             printf("NO
");
77             continue;
78         }
79         flag=0;
80         dfs(starex,starey,0);
81         if(flag==1)
82         printf("YES
");
83         else
84         printf("NO
");
85     }
86     return 0;
87 }

View Code