深度优先搜索和广度优先搜索（dfs and bfs）
程序员文章站
2022-05-22 21:00:09
...
走迷宫
深度搜索
第一行有两个数N M。N表示迷宫的行，M表示迷宫的列。接来下来N行M列为迷宫，0表示空地，1表示障碍物。最后一行4个数，前两个数为迷宫入口的x和y坐标。后两个为小哈的x和y坐标。
#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int book[51][51];
int minValue = 88888888;
int n,m;
int endx, endy;
void dfs(int x, int y, int step)
{
int next[4][2]={{0,1},{1,0},{0,-1},{1,0}};
int tx, ty;
if(x == endx && y == endy)
{
if(step < minValue)
minValue = step;
return;
}
for(int k = 0; k < 4; 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)
{
book[tx][ty]=1;
dfs(tx,ty,step+1);
book[tx][ty]=0;
}
}
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
scanf("%d",&a[i][j]);
int startx, starty;
scanf("%d%d%d%d", &startx, &starty, &endx, &endy);
book[startx][starty] = 1;
dfs(startx, starty, 0);
printf("%d", minValue);
return 0;
}
广度搜索
#include<bits/stdc++.h>
using namespace std;
struct node
{
int x;
int y;
int f;
int s;
};
int main()
{
struct node que[2501];
int head = 1;
int tail = 1;
int a[51][51]={0},book[51][51]={0};
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m;j++)
scanf("%d", &a[i][j]);
int startx, starty, endx, endy;
scanf("%d%d%d%d", &startx, &starty, &endx, &endy);
que[tail].x = startx;
que[tail].y = starty;
que[tail].f = 0;
que[tail].s = 0;
book[startx][starty] = 1;
int flag = 0;
tail++;
while(head<tail)
{
int tx,ty;
for(int k = 0; k < 4; k++)
{
tx = que[head].x+next[k][0];
ty = que[head].y+next[k][1];
// printf("tx is %d, ty is %d\n",tx,ty);
if(tx<1||tx>n||ty<1||ty>m)
continue;
if(a[tx][ty]==0 && book[tx][ty]==0)
{
book[tx][ty]=1;
que[tail].x=tx;
que[tail].y=ty;
que[tail].f=head;
que[tail].s=que[head].s+1;
tail++;
}
if(tx==endx && ty==endy)
{
flag=1;
break;
}
}
// printf("\n");
if(flag==1)
break;
head++;
}
if(flag == 1)
printf("%d",que[tail-1].s);
else
printf("No Way!");
return 0;
}
宝岛探险
广度搜索
#include<bits/stdc++.h>
using namespace std;
struct note
{
int x;
int y;
};
int main()
{
struct note que[2501];
int head = 1, tail = 1;
int a[51][51];
int book[51][51]={0};
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
int n,m,startx,starty;
scanf("%d%d%d%d",&n,&m,&startx,&starty);
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m;j++)
scanf("%d", &a[i][j]);
que[tail].x = startx;
que[tail].y = starty;
tail++;
book[startx][starty] = 1;
int sum=1;
while(head<tail)
{
int tx,ty;
for(int k = 0; k < 4; k++)
{
tx = que[head].x+next[k][0];
ty = que[head].y+next[k][1];
// printf("tx is %d, ty is %d\n",tx,ty);
if(tx<1||tx>n||ty<1||ty>m)
continue;
if(a[tx][ty]>0 && book[tx][ty]==0)
{
sum++;
book[tx][ty]=1;
que[tail].x=tx;
que[tail].y=ty;
tail++;
}
}
head++;
}
printf("%d",sum);
return 0;
}
深度搜索
#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int book[51][51]={0};
int n,m,sum;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x, int y)
{
int tx, ty;
for(int k = 0; k < 4; k++)
{
tx = x+next[k][0];
ty = y+next[k][1];
//printf("tx is %d, ty is %d\n",tx,ty);
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);
}
}
return;
}
int main()
{
int startx,starty;
scanf("%d%d%d%d",&n,&m,&startx,&starty);
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m;j++)
scanf("%d", &a[i][j]);
book[startx][starty] = 1;
sum=1;
dfs(startx,starty);
printf("%d",sum);
return 0;
}
输出结果
38
0000000000
0000111000
0000111100
0000011100
0000001110
0111011110
0111111110
0011111100
0001111000
0000000000
对结果进行着色
#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int book[51][51]={0};
int n,m,sum;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x, int y,int color)
{
a[x][y]=color;
int tx, ty;
for(int k = 0; k < 4; k++)
{
tx = x+next[k][0];
ty = y+next[k][1];
//printf("tx is %d, ty is %d\n",tx,ty);
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 startx,starty;
scanf("%d%d%d%d",&n,&m,&startx,&starty);
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m;j++)
scanf("%d", &a[i][j]);
book[startx][starty] = 1;
sum=1;
int color = -1;
dfs(startx,starty,color);
printf("%d\n",sum);
for(int i = 1; i <= n;i++)
{
for(int j = 1; j <= m;j++)
printf("%3d", a[i][j]);
printf("\n");
}
return 0;
}
输出：
10 10 6 8
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
38
1 2 1 0 0 0 0 0 2 3
3 0 2 0 -1 -1 -1 0 1 2
4 0 1 0 -1 -1 -1 -1 0 1
3 2 0 0 0 -1 -1 -1 0 0
0 0 0 0 0 0 -1 -1 -1 0
0 -1 -1 -1 0 -1 -1 -1 -1 0
0 -1 -1 -1 -1 -1 -1 -1 -1 0
0 0 -1 -1 -1 -1 -1 -1 0 0
0 0 0 -1 -1 -1 -1 0 1 2
0 0 0 0 0 0 0 0 1 0
Floodfill漫水填充法（种子填充法）
#include<bits/stdc++.h>
using namespace std;
int a[51][51];
int book[51][51]={0};
int n,m,sum;
int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
void dfs(int x, int y,int color)
{
a[x][y]=color;
int tx, ty;
for(int k = 0; k < 4; k++)
{
tx = x+next[k][0];
ty = y+next[k][1];
//printf("tx is %d, ty is %d\n",tx,ty);
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()
{
scanf("%d%d",&n,&m);
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m;j++)
scanf("%d", &a[i][j]);
int num = 0;
for(int i = 1; i <= n;i++)
for(int j = 1; j <= m;j++)
{
if(a[i][j]>0)
{
num--;
book[i][j]=1;
dfs(i,j,num);
}
}
printf("有%d小岛\n",-num);
for(int i = 1; i <= n;i++)
{
for(int j = 1; j <= m;j++)
printf("%3d", a[i][j]);
printf("\n");
}
return 0;
}
输出结果：
10 10
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
有4小岛
-1 -1 -1 0 0 0 0 0 -2 -2
-1 0 -1 0 -3 -3 -3 0 -2 -2
-1 0 -1 0 -3 -3 -3 -3 0 -2
-1 -1 0 0 0 -3 -3 -3 0 0
0 0 0 0 0 0 -3 -3 -3 0
0 -3 -3 -3 0 -3 -3 -3 -3 0
0 -3 -3 -3 -3 -3 -3 -3 -3 0
0 0 -3 -3 -3 -3 -3 -3 0 0
0 0 0 -3 -3 -3 -3 0 -4 -4
0 0 0 0 0 0 0 0 -4 0
上一篇： 深度优先搜索(Depth-First-Search,DFS)
下一篇： 工信部出手 违规APP危险了