DFS专题训练
分类:
IT文章
•
2025-02-03 22:57:07
参考书籍《算法竞赛入门到进阶》
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
