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

目录

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;
}