DFS专题训练

参考书籍《算法竞赛入门到进阶》

poj2386 题目链接 http://poj.org/problem?id=2386

注意理解题目中的所谓的池塘，记录搜索次数即可。

AC代码：

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 const int maxn=150;
 5 char a[maxn][maxn];
 6 int dx[8]={1,1,1,-1,-1,-1,0,0};
 7 int dy[8]={1,-1,0,1,-1,0,1,-1};
 8 int n,m;
 9 void dfs(int x,int y)
10 {
11     a[x][y]='.';
12     for (int i = 0; i < 8; ++i)
13     {
14         int nx = x+dx[i];
15         int ny = y+dy[i];
16         if (nx>=0&&nx<n&&ny>=0&&ny<m&&a[nx][ny]=='W') dfs(nx,ny);
17     }
18     return ;
19 }
20 int main(int argc, char const *argv[])
21 {
22     cin>>n>>m;
23     int res=0;
24     for (int i = 0; i < n; ++i)
25     {
26         for (int j = 0; j < m; ++j)
27         {
28             cin>>a[i][j];
29         }
30     }
31     for (int i = 0; i < n; ++i)
32     {
33         for (int j = 0; j < m; ++j)
34         {
35             if (a[i][j]=='W')
36             {
37                 dfs(i,j);
38                 res++;
39             }
40         }
41     }
42     cout<<res<<endl;
43     return 0;
44 }

View Code

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

经典深搜问题

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int n,tot=0;
 4 int col[12];
 5 bool check(int c,int r)
 6 {
 7     for (int i = 0; i < r; ++i)
 8     {
 9         if (col[i]==c||(abs(col[i]-c)==abs(i-r))) return false;        
10     }
11     return true;
12 }
13 void dfs(int r)
14 {
15     if (r==n)
16     {
17         tot++;
18         return ;
19     }
20     for (int c = 0; c < n; ++c)
21     {
22         if (check(c,r))
23         {
24             col[r]=c;
25             dfs(r+1);
26         }
27     }
28 }
29 int main(int argc, char const *argv[])
30 {
31     int ans[12]={0};
32     for (n = 0; n <= 10; ++n)
33     {
34         memset(col,0,sizeof(col));
35         tot=0;
36         dfs(0);
37         ans[n]=tot;
38     }
39     while(cin>>n)
40     {
41         if (n==0) return 0;
42         cout<<ans[n]<<endl;
43     }
44     return 0;
45 }

View Code

poj2531 题目链接：http://poj.org/problem?id=2531

题目要求两个集合中点的距离和最大，我们先假设都在一个集合，这样距离和为0，然后一个一个地往另外一个集合放，距离和变小则返回，变大继续，过程中不断更新最大值。

AC代码：

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 const int inf=0x3f3f3f3f;
 5 int a[25][25];
 6 int g[25];
 7 int res;
 8 int n;
 9 void dfs(int step,int sum)
10 {
11     g[step]=1;
12     int num=sum;
13     for (int i = 0; i < n; ++i)
14     {
15         if (g[i]==1) num-=a[step][i];
16         else num+=a[step][i];
17     }
18     res=max(res,num);
19     for (int i = step+1; i < n; ++i)
20     {
21         if (num>sum)
22         {
23             dfs(i,num);
24             g[i]=0;
25         }
26     }
27 }
28 int main(int argc, char const *argv[])
29 {
30     while(cin>>n)
31     {
32         memset(a,0,sizeof(a));
33         memset(g,0,sizeof(g));
34         for (int i = 0; i < n; ++i)
35         {
36             for (int j = 0; j < n; ++j)
37             {
38                 cin>>a[i][j];
39             }
40         }
41         res=-0x3f3f3f3f;
42         dfs(0,0);
43         cout<<res;
44     }
45     return 0;
46 }

View Code

poj1416 题目链接：http://poj.org/problem?id=1416

预处理能被切成的情况，然后深搜，借鉴了网上的AC代码

AC代码：

 1 #include <iostream>
 2 #include <algorithm>
 3 using namespace std;
 4 #define MAXN 10000
 5 int a,len,flag,rejected,k;
 6 string b;
 7 struct ss
 8 {
 9     int goal;
10     string str;
11 }score[MAXN],edge[10][10];
12 bool dfs(int now,int ret,string tmp_str)
13 {
14     if (ret>a||now>len) return false;
15     if (ret<=a&&now==len)
16     {
17         score[k].goal=ret;
18         score[k].str=tmp_str;
19         k++;
20         flag=1;
21         return true;
22     }
23     int next=now+1;
24     for (int i = next; i <=len; ++i) dfs(i,ret+edge[next][i].goal,tmp_str+" "+edge[next][i].str);
25 }
26 void build_map()
27 {
28     for (int i = 1; i <= len; ++i)
29     {
30         for (int j = i; j <= len; ++j)
31         {
32             if (i==j)
33             {
34                 edge[i][j].goal=b[i]-'0';
35                 edge[i][j].str=b[i];
36             }
37             else
38             {
39                 edge[i][j].goal=edge[i][j-1].goal*10+b[j]-'0';
40                 edge[i][j].str=edge[i][j-1].str+b[j];
41             }
42         }
43     }
44 }
45 bool cmp(ss aa,ss bb)
46 {
47     return aa.goal>bb.goal;
48 }
49 int main(int argc, char const *argv[])
50 {
51     while(cin>>a>>b)
52     {
53         if (!a&&b[0]=='0') break;
54         len = b.length();
55         b=" "+b;
56         build_map();
57         flag=rejected=0,k=1;
58         dfs(0,0,"");
59         if (k>1) sort(score+1,score+k,cmp);
60         if (score[1].goal==score[2].goal&&score[1].goal!=0) rejected=1;
61         if (flag&&!rejected) cout<<score[1].goal<<score[1].str<<endl;
62         else if (rejected) cout<<"rejected"<<endl;
63         else cout<<"error"<<endl;
64     }
65     return 0;
66 }

View Code

poj2676 题目链接：http://poj.org/problem?id=2676

九宫格，开三个数组，一个用来存同一行该数是否被用过，一个用来存同一列该数是否被用过，剩下一个用来存该宫格里是否被用过

AC代码：

 1 #include <iostream>
 2 #include <string.h>
 3 using namespace std;
 4 int mapp[10][10];//初始图
 5 bool h[10][10];//行
 6 bool l[10][10];//列
 7 bool g[10][10];//格
 8 bool flage=false;
 9 bool dfs(int x,int y)
10 {
11     if (x==9)
12     {
13         flage=true;
14         return true;
15     }
16     if (mapp[x][y])
17     {
18         if(y==8) dfs(x+1,0);
19         else dfs(x,y+1);
20         if (flage) return true;
21         else return false;
22     }
23     else
24     {
25         int k=x/3*3+y/3;
26         for (int i = 1; i <= 9; ++i)//遍历1-9的9个数字
27         {
28             if (!h[x][i]&&!l[y][i]&&!g[k][i])
29             {
30                 mapp[x][y]=i;
31                 h[x][i]=true;
32                 l[y][i]=true;
33                 g[k][i]=true;
34                 if(y==8) dfs(x+1,0);
35                 else dfs(x,y+1);
36                 if (flage)
37                 {
38                     return true;
39                 }
40                 else
41                 {
42                     mapp[x][y]=0;
43                     h[x][i]=false;
44                     l[y][i]=false;
45                     g[k][i]=false;
46                 }
47                 
48             }
49         }
50     }
51     return false;
52 }
53 int main(int argc, char const *argv[])
54 {
55     int t;
56     cin>>t;
57     while(t--)
58     {
59         memset(h,false,sizeof(h));
60         memset(l,false,sizeof(l));
61         memset(g,false,sizeof(g));
62         flage=false;
63         char c;
64         for (int i = 0; i < 9; ++i)
65         {
66             for (int j = 0; j < 9; ++j)
67             {
68                 cin>>c;
69                 mapp[i][j]=c-'0';
70                 if (mapp[i][j])
71                 {
72                     int k=i/3*3+j/3;
73                     h[i][mapp[i][j]]=true;
74                     l[j][mapp[i][j]]=true;
75                     g[k][mapp[i][j]]=true;
76                 }
77             }
78         }
79         if(dfs(0,0))
80         {
81             for (int i = 0; i < 9; ++i)
82             {
83                 for (int j = 0; j < 9; ++j)
84                 {
85                     cout<<mapp[i][j];
86                 }
87                 cout<<endl;
88             }
89         }
90     }
91     return 0;
92 }

View Code

poj1129 题目链接：http://poj.org/problem?id=1129

本题我没有使用深搜，用四色定理直接染色输出染色数即可，注意染同一颜色的是与其前被染的都不相邻才行，这是写代码时容易错的一个地方。

附样例：

5
A:BE
B:AC
C:BD
D:CE
E:AD

该样例应该输出3

AC代码：

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 struct node
 6 {
 7     char a;
 8     int number;
 9     bool f;
10 }aa[100];
11 bool mapp[30][30];
12 node bb[100];
13 int cmp(const node &a,const node &b)
14 {
15     return a.number>b.number;
16 }
17 int main(int argc, char const *argv[])
18 {
19     int t;
20     while(cin>>t)
21     {
22         memset(mapp,false,sizeof(mapp));
23         memset(aa,0,sizeof(aa));
24         string ss;
25         if (t==0) break;
26         else
27         {
28             for (int i = 0; i < t; ++i)
29             {
30                 cin>>ss;
31                 int len=ss.length();
32                 aa[i].a=ss[0];
33                 aa[i].number=len-2;
34                 aa[i].f=false;
35                 for (int j = 2; j < len; ++j)
36                 {
37                     mapp[ss[0]-'A'][ss[j]-'A']=true;
38                 }
39             }
40             sort(aa,aa+t,cmp);
41             int num=0;
42             for (int i = 0; i < t; ++i)
43             {
44                 if (aa[i].f==false)
45                 {
46                     int kk=0;
47                     memset(bb,0,sizeof(bb));
48                     aa[i].f=true;
49                     bb[kk].a=aa[i].a;
50                     kk++;
51                     num++;
52                     //cout<<num<<" "<<aa[i].a<<endl;
53                     for (int j = 0; j < t; ++j)
54                     {
55                         if (aa[i].a-'A'==j) continue;
56                         bool flage=true;
57                         for (int ii = 0; ii < kk; ++ii)
58                         {
59                             if (mapp[bb[ii].a-'A'][j]!=false)
60                             {
61                                 flage=false;
62                             }
63                         }
64                         if (flage)
65                         {
66                             for (int k = 0; k < t; ++k)
67                             {
68                                 if(aa[k].a==j+'A'&&aa[k].f==false)
69                                 {
70                                     aa[k].f=true;
71                                     bb[kk].a=aa[k].a;
72                                     kk++;
73                                     //cout<<aa[k].a<<endl;
74                                     break;
75                                 }
76                             }
77                         }
78                     }
79                 }
80             }
81             if (num==1)
82             {
83                 cout<<"1 channel needed."<<endl;
84             }
85             else
86             {
87                 cout<<num<<" channels needed."<<endl;
88             }
89         }
90     }
91     return 0;
92 }

View Code

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

注意记录转弯次数，判断是否在同一直线上，直接深搜即可

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int maze[1010][1010];
 4 bool vis[1010][1010];
 5 bool flage;
 6 int dx[4]={0,0,1,-1};
 7 int dy[4]={1,-1,0,0};
 8 int n,m,q,x1,y1,x2,y2;
 9 void dfs(int x,int y,int d,int t)
10 {
11     if (t>2||flage) return ;
12     if (t==2&&(x-x2)!=0&&(y-y2)!=0) return ;
13     if (x==x2&&y==y2&&t<=2)
14     {
15         flage=1;
16         return ;
17     }
18     for (int i = 0; i < 4; ++i)
19     {
20         int xx=x+dx[i];
21         int yy=y+dy[i];
22         if (xx<1||xx>n||yy<1||yy>m||vis[xx][yy]) continue;
23         if (maze[xx][yy]==0||(xx==x2&&yy==y2))
24         {
25             vis[xx][yy]=1;
26             if (d==-1||d==i) dfs(xx,yy,i,t);
27             else dfs(xx,yy,i,t+1);
28             vis[xx][yy]=0;
29         }
30     }
31     return ;
32 }
33 int main(int argc, char const *argv[])
34 {
35     while(cin>>n>>m)
36     {
37         if (n+m==0) break;
38         memset(maze,0,sizeof(maze));
39         for (int i = 1; i <= n; ++i)
40         {
41             for (int j = 1; j <= m; ++j)
42             {
43                 cin>>maze[i][j];
44             }
45         }
46         cin>>q;
47         for (int i = 0; i < q; ++i)
48         {
49             cin>>x1>>y1>>x2>>y2;
50             memset(vis,0,sizeof(vis));
51             flage=0;
52             if (maze[x1][y1]==maze[x2][y2]&&maze[x1][y1])
53             {
54                 dfs(x1,y1,-1,0);
55             }
56             if (flage) cout<<"YES"<<endl;
57             else cout<<"NO"<<endl;
58         }
59     }
60     return 0;
61 }

View Code

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

注意理解题目，已经输出行末不能有空格

AC代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int visited[10][10];
 4 int a[100];
 5 int n,m,k;
 6 bool flag=false;
 7 void dfs(int x,int y,int nn)
 8 {
 9     for (int i = 1; i <= k; ++i)
10     {
11         if ((nn+1)<2*a[i]) return ;
12     }
13     if (nn==0)
14     {
15         flag=true;
16         return ;
17     }
18     else
19     {
20         for (int i = 1; i <= k; ++i)
21         {
22             if (visited[x-1][y]!=i&&visited[x][y-1]!=i&&a[i]!=0)
23             {
24                 visited[x][y]=i;
25                 a[i]--;
26                 if (y==m) dfs(x+1,1,nn-1);
27                 else dfs(x,y+1,nn-1);
28                 if (flag) return ;
29                 else
30                 {
31                     visited[x][y]=0;
32                     a[i]++;
33                 }
34             }
35             
36         }
37     }
38     return ;
39 }
40 int main(int argc, char const *argv[])
41 {
42     int t;
43     cin>>t;
44     for (int kk = 1; kk <= t; ++kk)
45     {
46         flag=false;
47         memset(visited,0,sizeof(visited));
48         memset(a,0,sizeof(a));
49         cin>>n>>m>>k;
50         for (int i = 1; i <= k; ++i)
51         {
52             cin>>a[i];
53         }
54         dfs(1,1,n*m);
55         if(flag)
56         {
57             cout<<"Case #"<<kk<<":"<<endl;
58             cout<<"YES"<<endl;
59             for (int i = 1; i <= n; ++i)
60             {
61                 for (int j = 1; j <= m; ++j)
62                 {
63                     if (j!=1) cout<<" ";
64                     cout<<visited[i][j];
65                 }
66                 cout<<endl;
67             }
68         }
69         else
70         {
71             cout<<"Case #"<<kk<<":"<<endl;
72             cout<<"NO"<<endl;
73         }
74     }
75     return 0;
76 }

View Code

poj3134 题目链接：http://poj.org/problem?id=3134

（按书上写的）

 1 #include <iostream>
 2 //#include <stdlib.h>
 3 using namespace std;
 4 int val[1010];
 5 int pos,n;
 6 bool ida(int now,int depth)
 7 {
 8     if (now>depth) return false;
 9     if (val[pos]<<(depth-now)<n) return false;
10     if (val[pos] == n) return true;
11     pos++;
12     for (int i = 0; i < pos; ++i)
13     {
14         val[pos] = val[pos-1] + val[i];
15         if (ida(now + 1,depth)) return true;
16         val[pos] = val[pos-1] - val[i];
17         if (ida(now + 1,depth)) return true;
18     }
19     pos --;
20     return false;
21 }
22 int main(int argc, char const *argv[])
23 {
24     int t;
25     while(cin>>n&&n)
26     {
27         int depth;
28         for (depth = 0; ; ++depth)
29         {
30             val[pos = 0] = 1;
31             if (ida(0,depth)) break;
32         }
33         cout<<depth<<endl;
34     }
35     return 0;
36 }

View Code