BFS+DFS题目_14
1
3e6aa1cf6422df1d6282

作者：Cpp五条 | 2024-04-14 22:37:11

踩

14
1
3e6aa1cf6422df1d62822db7ada98c48ebb6586adb

BFS 红黑瓷砖

#include <iostream> #include <algorithm> #include <queue> using namespace std; #define check(x,y) (x<Wx && x>=0 && y>=0 && y<Hy) char room[23][23]; int dir[4][2]={{-1,0},{0,-1},{1,0},{0,1}}; int Wx,Hy,num; struct node{int x,y;}; void bfs(int dx,int dy) { num=1; queue<node>q; node start,next; start.x=dx; start.y=dy; q.push(start); while(!q.empty()){ start=q.front(); q.pop(); for(int i=0;i<4;i++){ next.x=start.x+dir[i][0]; next.y=start.y+dir[i][1]; if(check(next.x,next.y) && room[next.x][next.y]=='.'){ room[next.x][next.y]='#'; num++; q.push(next); } } } } int main() { int x,y,dx,dy; while(cin>>Wx>>Hy){ if(Wx==0 &&Hy==0) break; for(y=0;y<Hy;y++){ for(x=0;x<Wx;x++){ cin>>room[x][y]; if(room[x][y]=='@') {dx=x,dy=y;} } } num=0; bfs(dx,dy); cout<<num<<endl; } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

DFS+染色法----油田

#include <iostream> #include <algorithm> #include <cstring> using namespace std; int n,m; char a[101][101]; int vis[101][101]; void dfs(int x,int y,int color) { int next[8][2]={{0,1},{-1,-1},{-1,1},{1,-1},{1,1},{1,0},{-1,0},{0,-1}}; a[x][y]=color; for(int i=0;i<8;i++) { int tx=x+next[i][0]; int ty=y+next[i][1]; if(tx<1 || tx>n || ty<1 || ty>m) continue; if(a[tx][ty]=='@' && vis[tx][ty]==0) { vis[tx][ty]=1; dfs(tx,ty,color); } } return; } int main() { while(cin>>n>>m && m) { for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; memset(vis,0,sizeof(vis)); int num=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(a[i][j]=='@') { num--; vis[i][j]=1; dfs(i,j,num); } cout<<-num<<endl; } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

DFS+剪枝----陷落迷宫

#include <iostream> #include <algorithm> #include <cstring> using namespace std; int n,m,t,sx,sy,ex,ey,flag,sum=0; char a[8][8]; int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1},book[8][8]; void dfs(int x,int y,int step) { if(step==t && a[x][y]=='D') { flag=1; return; } if(flag) return; if(step>t) return; if((abs(ex-sx)+abs(ey-sy))%2 != t%2) return; for(int i=0;i<4;i++) { int tx=x+dx[i]; int ty=y+dy[i]; if(tx<1 || tx>n || ty<1 || ty>m) continue; if(a[tx][ty]!='X' && !book[tx][ty]) { book[tx][ty]=1; dfs(tx,ty,step+1); book[tx][ty]=0; } } } int main() { while(cin>>n>>m>>t && n||m||t){ memset(book,0,sizeof(book)); sum=0; flag=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { cin>>a[i][j]; if(a[i][j]=='S'){ sx=i;sy=j; } else if(a[i][j]=='D'){ ex=i;ey=j; } else if(a[i][j]=='X') sum++; } if(n*m-sum<=t) { cout<<"NO"<<endl; continue; } book[sx][sy]=1; dfs(sx,sy,0); if(flag) cout<<"YES"<<endl; else cout<<"NO"<<endl; } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

DFS+路径输出----走迷宫

#include <iostream> #include <algorithm> using namespace std; int n,m,sx,sy,ex,ey,flag; //flag用来表示是否存在路径 int a[15][15]; //地图，因为本身就是1或0，所以可以利用而省去标记数组 int ans[50000][2]; //存储解 int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0}; //方向一定是左下右上 void print(int n) //打印解 { flag=1; //有解 for(int i=1;i<=n;i++) { if(i<n) printf("(%d,%d)->",ans[i][0],ans[i][1]); else printf("(%d,%d)\n",ans[i][0],ans[i][1]); } } void dfs(int an,int x,int y) //an表示ans[][]的一维下标 { for(int i=0;i<4;i++) //直接尝试 { a[x][y]=0; //标记a(x,y)已经走过并不再可走，避免重复走，可以这么做的原因是dfs的x,y参数初始必然可走，即为1 x=x+dx[i]; //尝试下一点 y=y+dy[i]; if(a[x][y]) { ans[an][0]=x; ans[an][1]=y; if(x==ex && y==ey) print(an); else dfs(an+1,x,y); } x-=dx[i]; y-=dy[i]; a[x][y]=1; //回溯 } } int main() { cin>>n>>m; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>a[i][j]; cin>>sx>>sy>>ex>>ey; ans[1][0]=sx,ans[1][1]=sy; dfs(2,sx,sy); if(!flag) printf("-1"); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

BFS----逃离迷宫

#include <iostream> #include <algorithm> #include <queue> #include <cstring> using namespace std; int n,m,t,xx,yy,ans=0,book[505][505][2]; char a[505][505]; struct node { int x,y,f; }; int dx[4]={-1,0,1,0}; int dy[4]={0,1,0,-1}; int bfs(int x,int y) { memset(book,-1,sizeof(book)); queue <node>q; book[x][y][0]=0; q.push((node){xx,yy,0}); while(!q.empty()) { node h; h=q.front(); q.pop(); if(h.f && a[h.x][h.y]=='E') { return ans=book[h.x][h.y][1]; } for(int i=0;i<4;i++) { int tx=h.x+dx[i]; int ty=h.y+dy[i]; if(tx>=1 && tx<=n && ty>=1 && ty<=m && a[tx][ty]!='#') { node temp; if(a[tx][ty]=='K') temp.f=1;//取得钥匙; else temp.f=h.f; //先前已有钥匙temp.f也会为1，没有为0 if(book[tx][ty][temp.f]!=-1) continue; //已走过，continue; if(a[tx][ty]=='E' && h.f==0) continue; //遇到E但是没有钥匙，continue; temp.x=tx; temp.y=ty; book[tx][ty][temp.f]=book[h.x][h.y][h.f]+1; //步数累加 q.push(temp); } } } return -1; } int main() { cin>>t; while(t--){ cin>>n>>m; ans=0; memset(a,0,sizeof(a)); for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { scanf(" %c",&a[i][j]); if(a[i][j]=='P') {xx=i,yy=j;} } } ans=bfs(xx,yy); if(ans>0) cout<<ans<<endl; else cout<<"No solution"<<endl; } return 0; } /*#include<cstdio> #include<cstring> #include<algorithm> #include<queue> using namespace std; int N,M; char map[503][503]; int vis[502][502][2]; int d[4][2]={0,1,0,-1,1,0,-1,0}; struct Node{ int x,y; int f; }; int bfs(int x,int y) { memset(vis,-1,sizeof(vis)); queue<Node> q; Node p; p.x=x,p.y=y,p.f=0; vis[x][y][p.f]=0; q.push(p); while(!q.empty()) { p=q.front();q.pop(); if(map[p.x][p.y]=='E'&&p.f) return vis[p.x][p.y][1]; for(int i=0;i<4;i++) { int tx=p.x+d[i][0],ty=p.y+d[i][1]; if(tx>=0&&tx<N&&ty>=0&&ty<M&&map[tx][ty]!='#') { Node temp; if(map[tx][ty]=='K') temp.f=1; else temp.f=p.f; if(vis[tx][ty][temp.f]!=-1) continue; if(map[tx][ty]=='E'&&temp.f==0) continue; temp.x=tx,temp.y=ty; vis[tx][ty][temp.f]=vis[p.x][p.y][p.f]+1; q.push(temp); } } } return -1; } int main() { int T; scanf("%d",&T); while(T--) { scanf("%d%d",&N,&M); for(int i=0;i<N;i++) scanf("%s",map[i]); int ans; for(int i=0;i<N;i++) for(int j=0;j<M;j++) if(map[i][j]=='P') { ans=bfs(i,j);break; } if(ans>0) printf("%d\n",ans); else printf("No solution\n"); } return 0; } */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149

DFS----单词接龙

#include <iostream> #include <string> #include <algorithm> using namespace std; string s[21]; int vis[21],maxl=0,n; bool judge(string s1,string s2,int j) //判断是否有长度为j的相同部分 { int e=s1.length(); string s3(s1,e-j); string s4(s2,0,j); if(s3==s4) return true; return false; } string link(string s1,string s2,int j) { int l1=s1.length(); string s3(s1,0,l1-j); string s4=s3+s2; return s4; } void dfs(string ss) { int sl=ss.length(); maxl=max(maxl,sl); for(int i=0;i<n;i++) for(int j=1;j<=ss.length();j++){ if(vis[i]>=2) continue; if(j>s[i].length()) continue; if(judge(ss,s[i],j)){ vis[i]++; string temp=link(ss,s[i],j); dfs(temp); vis[i]--; } } } int main() { cin>>n; for(int i=0;i<n;i++) cin>>s[i]; string b; cin>>b; dfs(b); cout<<maxl<<endl; return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

DFS+染色法

#include <stdio.h> int a[101][101]; int book[110][110],n,m,sum; void dfs(int x,int y,int color) { int next[4][2]={{0,1},//right {1,0},//down {-1,0},//up {0,-1}//left }; int k,tx,ty; a[x][y]=color; for(k=0;k<=3;k++) { tx=x+next[k][0]; ty=y+next[k][1]; if(tx<1 || tx>n || ty<1 || ty>m) continue; if(a[tx][ty]>0 && book[tx][ty]==0) { sum++; book[tx][ty]=1; dfs(tx,ty,color); } } return; } int main() { int i,j,num=0; scanf("%d %d\n",&n,&m); for(i=1;i<=n;i++) { for(j=1;j<=m;j++) scanf("%1d",&a[i][j]); } //对大于0的点进行染色 for(i=1;i<=n;i++) { for(j=1;j<=m;j++) { if(a[i][j]>0) { num--; book[i][j]=1; dfs(i,j,num); } } } printf("%d",-num); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

DFS----图腾

#include <iostream> #include <algorithm> #include <cstring> using namespace std; int n; char s[1025][1025]; void dfs(int k,int x,int y) { if(k==1) { s[x][y]='/'; s[x][y+1]='_'; s[x][y+2]='_'; s[x][y+3]='\\'; s[x-1][y+1]='/'; s[x-1][y+2]='\\'; return ; } dfs(k-1,x,y); dfs(k-1,x,y+(1<<k)); dfs(k-1,x-(1<<k-1),y+(1<<k-1)); } int main() { int n; cin>>n; memset(s,(' '),sizeof(s)); dfs(n,1<<n,1); for(int i=1;i<=(1<<n);i++) { for(int j=1;j<=(1<<n+1);j++) cout<<s[i][j]; if(i!=(1<<n)) cout<<endl; } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

数的全排列

#include <iostream> typedef long long ll; using namespace std; int n,a[8],book[8]={0}; void dfs(int x) { if(x==n+1) { for(int i=1;i<=n;i++) printf(" %d",a[i]); printf("\n"); return; } for(int i=1;i<=n;i++) { if(book[i]==0) { a[x]=i; book[i]=1; dfs(x+1); book[i]=0; } } return; } int main() { cin>>n; dfs(1); return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/Cpp五条/article/detail/424444

推荐阅读

相关标签

BFS+DFS题目_1413e6aa1cf6422df1d6282

BFS 红黑瓷砖

DFS+染色法----油田

DFS+剪枝----陷落迷宫

DFS+路径输出----走迷宫

BFS----逃离迷宫

DFS----单词接龙

DFS+染色法

DFS----图腾

数的全排列

BFS+DFS题目_14
1
3e6aa1cf6422df1d6282