HDU--1010

原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1010
分析：dfs+奇偶剪枝。
Tempter of the Bone
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 char s[10][10];
 7 bool visit[10][10],flag;
 8 int dx[4]={0,0,1,-1};
 9 int dy[4]={-1,1,0,0};
10 int n,m,t,di,dj;
11 void dfs(int time,int i,int j)
12 {
13     if(t>=n*m)return;
14     if(time==t)
15     {
16         if(s[i][j]=='D')flag=true;
17         return;
18     }
19     int temp=abs(i-di)+abs(j-dj);
20         temp=t-temp-time;
21         if(temp&1)return;
22     for(int k=0;k<4;k++)
23     {
24         int nx=i+dx[k],ny=j+dy[k];
25         if(!visit[nx][ny]&&nx>=0&&ny>=0&&nx<n&&ny<m&&!flag&&s[nx][ny]!='X')
26         {
27             visit[nx][ny]=true;
28             dfs(time+1,nx,ny);
29             visit[nx][ny]=false;
30         }
31         
32     }
33 }
34 int main()
35 {
36     while(~scanf("%d%d%d",&n,&m,&t))
37     {
38         if(n==0&&m==0&&t==0)break;
39         memset(visit,false,sizeof(visit));
40         for(int i=0;i<n;i++)
41         scanf("%s",s[i]);
42         flag=false;
43         int p,q,k=0;
44         for(int i=0;i<n;i++)
45         for(int j=0;j<m;j++)
46         {
47             if(s[i][j]=='S')
48             {
49                  visit[i][j]=true;
50                  p=i;q=j;
51             }
52             if(s[i][j]=='D')
53             {
54                 di=i;dj=j;
55             }
56             if(s[i][j]=='X')k++;
57         }
58         if(n*m-k-1>=t)dfs(0,p,q);
59         if(flag)printf("YES
");
60         else printf("NO
");
61     }
62     return 0;
63 }
View Code