HDOj 1010 DFS优化

 1 #include<cstdio>
 2 #include<cstring>
 3 int sx[4]={0,1,0,-1};
 4 int sy[4]={1,0,-1,0};
 5 int g[10][10];
 6 int x1,y1,x2,y2;
 7 int step;
 8 int n,m,t;
 9 void dfs(int x,int y,int c_step)
10 {
11     
12     if(x==x2&&y==y2&&c_step==t)
13     {
14         
15         step=1;return;
16     }
17     if((x>x2?x-x2:x2-x)+(y>y2?y-y2:y2-y)+c_step>t)//小剪
18     {
19         return;
20     }
21     int i;
22     for(i=0;i<4;i++)
23     {
24         int xx,yy;
25         xx=x+sx[i];
26         yy=y+sy[i];
27         if(xx>=1&&xx<=n&&yy>=1&&yy<=m&&g[xx][yy]==0&&c_step+1<=t)
28         {
29             g[xx][yy]=1;
30             dfs(xx,yy,c_step+1);
31             if(step==1)//强力缩短时间
32                 return;
33             g[xx][yy]=0;
34         }
35     }
36     
37 }
38 int main()
39 {
40     int i,j,sum;
41     char c;
42     while(scanf("%d %d %d",&n,&m,&t)!=EOF)
43     {
44         if(!n&&!m&&!t)break;
45         step=0;
46         sum=0;
47         getchar();
48         for(i=1;i<=n;i++)
49         {
50             for(j=1;j<=m;j++)
51             {
52                 c=getchar();
53                 if(c=='S')
54                     x1=i,y1=j;
55                 else if(c=='D')
56                     x2=i,y2=j,g[i][j]=0;
57                 else if(c=='X')
58                     g[i][j]=1;
59                 else if(c=='.')
60                     g[i][j]=0,sum++;
61             }
62             getchar();
63         }
64         if(sum+1<t||(t+x1+y1+x2+y2)%2==1)//奇偶性判别与可达性判别
65             printf("NO
");
66         else
67         {
68             g[x1][y1]=1;
69             dfs(x1,y1,0);
70             if(step)
71                 printf("YES
");
72             else
73                 printf("NO
");
74         }
75     }
76     return 0;
77 }
View Code