搜索(2):宽度优先搜索

发布时间:2024年01月23日

目录

1.宽度优先搜索(BFS)

2.马的遍历(经典宽搜)

? 2.1 建图

2.2 宽搜

2.3 完整代码

3.洛谷BFS

3.1 奇怪的电梯

3.2 Meteor Shower


1.宽度优先搜索(BFS)

? ? ?宽搜从根进入,向下逐层扩展,逐层访问

? ? ?宽搜是通过队列来实现的,用queue创建一个队列。宽搜的过程,通过队列来维护序列的状态空间,入队就排队等待,出队就将儿子们入队。

? ? ?宽搜的计算:出队后,入队前,结束后。

2.马的遍历(经典宽搜)

? 2.1 建图

? ? ? 对于最少步数的问题,我们建的图存的是到达该位置的最少步数,而队列的结构体元素存的是图中每个点的坐标,并进行判重

? ? ? dx[4],dy[4]存方向偏移量,因为走到每个格子,我们又有四个方向可以走,需要枚举每个方向

? ? ? 格子就是点,格子到格子就是边

const int N=410;
int n,m,x,y;
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={-2,-1,1,2,2,1,-1,-2};
struct node{int x,y;};
queue<node>q;//存点的坐标
int f[N][N],vis[N][N];//存步数和判重

2.2 宽搜

? ? ?从起点开始,先将起点入队并标记,之后开始宽搜,每次将队首元素出队,搜索它的周围元素,如果没有走过则进行标记,这是判重,因为之后再到这个位置的步数肯定比之前要多,所以我们标记之后就不会再搜索这个位置,然后将存步数的数组对该位置加1,之后将其压入队中,这是向外辐射扩散的。

void bfs(int x,int y)
{
  q.push({x,y});
  vis[x][y]=1;
  while(q.size())
 {
   auto u=q.front();
   q.pop();
   for(int i=0;i<8;i++)
   {
     int a=u.x+dx[i],b=u.y+dy[i];
     if(a<1||a>n||b<1||b>m||vis[a][b])continue;
     vis[a][b]=1;
     f[a][b]=f[u.x][u.y]+1;
     q.push({a,b});
   }
  }
}

2.3 完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=410;
int n,m,x,y;
int dx[8]={-1,-2,-2,-1,1,2,2,1};
int dy[8]={-2,-1,1,2,2,1,-1,-2};
struct node{int x,y;};
queue<node>q;//存点的坐标
int f[N][N],vis[N][N];//存步数和判重
void bfs(int x,int y)
{
  q.push({x,y});
  vis[x][y]=1;
  while(q.size())
 {
   auto u=q.front();
   q.pop();
   for(int i=0;i<8;i++)
   {
     int a=u.x+dx[i],b=u.y+dy[i];
     if(a<1||a>n||b<1||b>m||vis[a][b])continue;
     vis[a][b]=1;
     f[a][b]=f[u.x][u.y]+1;
     q.push({a,b});
   }
  }
}
int main()
{
  cin>>n>>m>>x>>y;
  memset(f,-1,sizeof f);
  f[x][y]=0;
  bfs(x,y);
  for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
         printf("%-5d",f[i][j]);
     printf("\n");
  return 0;
}

3.洛谷BFS

? ? 宽度优先搜索解决的就是最少步数问题,也可以用来解决方案数问题,但更倾向于用DFS。

3.1 奇怪的电梯

? ? ?这个题只有两个偏移方向,可以把这个电梯放倒,只有向左和向右两个方向。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 210;
int n, a, b;
queue<int>q;
int g[N], vis[N];//需要判重,因为一旦之前已经到达,那么之后再到达的步数一定大于之前到达的步数
int d[N];

void bfs(int a, int target)
{
    q.push(a);
    while (q.size())
    {
        auto u = q.front();
        if (a == target)return;
        q.pop();
        int nr = u + d[u], nl = u - d[u];
        if (nr >= 1 && nr <= n && !vis[nr]) g[nr] = g[u] + 1,vis[nr]=1,q.push(nr);
        if (nl >= 1 && nl <= n && !vis[nl]) g[nl] = g[u] + 1,vis[nl]=1,q.push(nl);
    }
}
int main()
{
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)cin >> d[i];
    memset(g, -1, sizeof g);
    g[a] = 0;
    bfs(a, b);
    cout << g[b];
    return 0;
}

3.2 Meteor Shower

? ? ? 这个题的难点在于如何避免贝茜在时刻t到达某个土地时这块土地还没有被撞击或烧焦,要想到达一个安全的格子,这个格子没有被流星撞击或烧焦,我们用数组来表示。

? ? ?还有某块土地会有多块陨石撞击或烧焦,我们选择最小的时刻。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 305;
struct node
{
	int x, y, time;
} p; 
int m, x, y, t, nx, ny, time1[N][N], vis[N][N]; 
int dx[4] = { 0,0,1,-1 }, dy[4] = { 1,-1,0,0 };
queue<node>q;
int main()
{
	cin >> m;
	memset(time1, -1, sizeof time1);
	for (int i = 1; i <= m; i++)
	{
		cin >> x >> y >> t;
		if (t < time1[x][y] || time1[x][y] == -1) //如果该时间小于之前被撞击的时间或者还没有被撞击,更新时间
			time1[x][y] = t;
		for (int i = 0; i < 4; i++)
		{
			nx = x + dx[i], ny = y + dy[i];
			if (nx >= 0 && ny >= 0 && (time1[nx][ny] == -1 || t < time1[nx][ny]))
				time1[nx][ny] = t;  //枚举焦土 
		}
	}
	q.push({ 0,0,0 }), vis[0][0] = 1;
	q.push(p);
	while (!q.empty())
	{
		p = q.front(); 
		q.pop();
		for (int i = 0; i < 4; i++)
		{
			nx = p.x + dx[i], ny = p.y + dy[i];
			if (nx >= 0 && ny >= 0 && vis[nx][ny] == 0 && (time1[nx][ny] == -1 || p.time + 1 < time1[nx][ny])) //没有流星到过或者贝茜到这个格子的时候流星还没有到达 
			{
				q.push({nx,ny,p.time+1});
				if (time1[nx][ny] == -1) //判断当前的格子是否安全 
				{
					cout << p.time+1 << endl;
					return 0;
				}
			}
		}
	}
	cout << -1 << endl; //到不了安全的格子就输出-1 
	return 0;
}
文章来源:https://blog.csdn.net/pancodearea/article/details/135781241
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。