搜索（DFS）

不知道为什么~除了我室友其他的同学都觉得DFS很简单~且比BFS容易得多........我真心不觉得啊T T~我真心觉得BFS比DFS简单得多................= =

为了把DFS完全搞懂，决定做一些DFS的题目.......

HDU 2181 哈密顿绕行世界问题

题意：

给出每个城市与之相连的三个城市的编号，求出给定城市环游所有城市，并回到给定城市的所有路线~按字典序输出~

是一道简单的DFS题目~只要注意输出的第一个和最后一个都是给定城市，以及哈密顿所走城市数即可~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int a[21][3],b[21],c[21],n,cas;
 7 
 8 void DFS(int x,int step)
 9 {
10   int i,j,t;
11   for(i=0;i<3;i++)
12   {
13     t=a[x][i];
14     if(t==n && step==20)
15     {
16       printf("%d: ",++cas);
17       for(j=1;j<=21;j++)
18         printf(" %d",c[j]);
19       printf("
");
20     }
21     else
22       if(b[t]==0)
23       {
24         b[t]=1;
25         c[step+1]=t;
26         DFS(t,step+1);
27         b[t]=0;
28       }
29   }
30   return;
31 }
32 
33 int main()
34 {
35   int i;
36   for(i=1;i<=20;i++)
37     scanf("%d%d%d",&a[i][0],&a[i][1],&a[i][2]);
38   while(scanf("%d",&n),n)
39   {
40     cas=0;
41     memset(b,0,sizeof(b));
42     b[n]=1;
43     c[1]=c[21]=n;
44     DFS(n,1);
45   }
46   return 0;
47 }

//memory：228KB time：0ms

HDU 1312 Red and Black

题意:找出与'@'相连的'.'的个数（'@'也算在内~）

也可以用BFS做，不过是在练DFS嘛~就只写了DFS的代码~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 using namespace std;
 6 
 7 int m,n,number,add[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
 8 char a[40][40];
 9 
10 void DFS(int x,int y,int step)
11 {
12   int i,hx,hy;
13   for(i=0;i<4;i++)
14   {
15     hx=x+add[i][0];
16     hy=y+add[i][1];
17     if(a[hx][hy]=='.')
18     {
19       a[hx][hy]='#';
20       number++;
21       DFS(hx,hy,step+1);
22     }
23   }
24 }
25 
26 int main()
27 {
28   int i,j;
29   while(scanf("%d%d",&m,&n),m,n)
30   {
31     memset(a,0,sizeof(a));
32     for(i=0;i<n;i++)
33       scanf("%s",a[i]);
34     for(i=0;i<n;i++)
35       for(j=0;j<m;j++)
36         if(a[i][j]=='@')
37         {
38             number=1;
39             DFS(i,j,0);
40             break;
41         }
42     printf("%d
",number);
43   }
44   return 0;
45 }

//memory：232KB time：15ms

WA一次是地图开小了一点~~~

HDU 1010 Tempter of the Bone

题意：给出出发点'S'、结束点'D'以及时间Time，看是否能恰好在Time时间上由'D'到达'S'上。其中'X'是不能走的~

在此题上要注意剪枝~我由于没有剪枝，结果TLE了......T T

看了网上的结题报告，发现要用到”奇偶剪枝“~~~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 char a[10][10];
 8 int m,n,time,temp,x1,x2,y1,y2,minn,add[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
 9 bool ID;
10 
11 void DFS(int x,int y,int step)
12 {
13   int i,hx,hy;
14   if(x<=0 || y<=0 || x>m || y>n || step>time)
15     return;
16   if(x==x2 && y==y2 && step==time)
17   {
18       ID=true;
19       return;
20   }
21   if(ID) return;
22   temp=time-step-abs(x-x2)-abs(y-y2);
23   if(temp<0 || temp&1) return;
24   for(i=0;i<4;i++)
25   {
26       hx=x+add[i][0];
27       hy=y+add[i][1];
28       if(a[hx][hy]!='X')
29       {
30           a[hx][hy]='X';
31           DFS(hx,hy,step+1);
32           a[hx][hy]='.';
33       }
34   }
35   return;
36 }
37 
38 int main()
39 {
40   int i,j,k;
41   while(scanf("%d%d%d",&m,&n,&time),m,n,time)
42   {
43  //   memset(a,0,sizeof(a));
44     ID=false;
45     k=0;
46     for(i=1;i<=m;i++)
47       for(j=1;j<=n;j++)
48       {
49         cin>>a[i][j];
50         if(a[i][j]=='S')
51         {
52           x1=i;
53           y1=j;
54         }
55         if(a[i][j]=='D')
56         {
57             x2=i;
58             y2=j;
59         }
60         if(a[i][j]=='X')
61             ++k;
62       }
63     if(m*n-k<=time)
64     {
65         printf("NO
");
66         continue;
67     }
68     a[x1][y1]='X';
69     DFS(x1,y1,0);
70     if(ID) printf("YES
");
71     else printf("NO
");
72   }
73   return 0;
74 }