广度优先搜索BFS

广度优先搜索BFS

广度优先搜索BFS

广度优先搜索(以下简称BFS)是搜索技术中常用的一种搜索。
BFS体现在广度一词上,一层一层进行遍历,常见的有在矩阵(二维数组)上的遍历以及树和图的遍历。体现在二维数组的遍历顺序如下(假设起点在左上),在只能上下左右四个方向遍历时,序号代表遍历顺序。

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

序号相同的位置访问顺序可任意。实现时,当访问1号位置时,就要对两个2号位置进行标记(我要准备访问你了),当访问任一个2号位置时就要标记它能访问到的3号位置,依次类推。
实现:对于一层一层遍历的结构,我们使用队列queue这一先进先出的数据结构。
首先1入队,遍历与1相邻的位置,即两个2入队,然后1出队,然后遍历与队尾2相邻的位置,将其入队(此时还有一个2号位置没遍历,但是不用担心,刚入队的3号位置在队首,不会影响层层遍历的光系),队尾2出队,此时队尾仍然是2号位置,此时访问该2号位置,将与其相邻且没遍历过位置入队,此时所有的3号位置全部入队,然后该2号位置出队。依此遍历至最后。

对于树结构的遍历其实就是对数结构的层序遍历,一层一层遍历
广度优先搜索BFS
黑色字体代表结点序号,红色字体为遍历层序。
首先遍历根结点,然后还是两个2号根结点的叶子结点入队遍历方式与矩阵相似。

图结构的遍历也类似
广度优先搜索BFS

//模板
int v[Max][Max];//标记数组,标记某位置是否已经访问
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
struct A
{
    int x,y,t;//x,y表示位置坐标,t表示遍历序号(依题而异),
}root,top;//结构体表示每一个位置
void bfs(int x,int y)//x,y传入起始位置坐标
{
    root.x=x;
    root.y=y;
    root.t=0;
    queue<A>Q;
    Q.push(root);//起始位置入队
    v[x][y]=1;//标记起始位置已经访问
    while(!Q.empty())
    {
        top=Q.front();
        Q.pop();
        v[top.x][top.y]=1;
        for(int i=0;i<4;i++)//遍历当前访问结点相邻结点
        {
            int nx=top.x+dx[i];
            int ny=top.y+dy[i];
            int nt=top.t+1;//与当前访问结点相邻点访问序号+1
            if(nx<1||nx>n||ny<1||ny>m) continue;//约束,防止数组越界
            ans[nx][ny]=nt;//记录每个位置的访问序号,依题而异
            if(...){}
            if(!v[nx][ny])//未被访问,入队等待访问
            {
            root.x=nx;
            root.y=ny;
            root.t=nt;
            Q.push(root);
            v[nx][ny]=1;
            }
        }
    }
}

例题:
力扣1293:
网格中的最短路径
给你一个 m * n 的网格,其中每个单元格不是 0(空)就是 1(障碍物)。每一步,您都可以在空白单元格中上、下、左、右移动。如果您 最多 可以消除 k 个障碍物,请找出从左上角 (0, 0) 到右下角 (m-1, n-1) 的最短路径,并返回通过该路径所需的步数。如果找不到这样的路径,则返回 -1。
输入1:
grid =
[[0,0,0],
[1,1,0],
[0,0,0],
[0,1,1],
[0,0,0]],
k = 1
输出2:6
输入2:
grid =
[[0,1,1],
[1,1,1],
[1,0,0]],
k = 1
输出2:-1
来源:力扣(LeetCode)
原题链接

思考
思路自然是深搜,值得注意的是如果v数组跟平常一样只设置二维,可能从一条路径经过i,j这个点出不去,而此时v[i][j]被标记为访问过,可能正确答案包含的路径却偏偏包含i,j这个点,这就无法得到正确答案咯;这时我们可以开一个三维v数组,表示每次经过该点时经过的障碍点的次数。

AC代码:

class Solution {
public:
    struct A
{
    int x,y,k,ans;
}root,top;
int n,m,K;
int ans=10000;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int a[100][100];
bool v[50][50][1600];
void bfs()
{
      root.x=0;
      root.y=0;
      root.k=K;
      root.ans=0;
      v[0][0][K]=1;
      queue<A>Q;
      Q.push(root);
      while(!Q.empty())
      {
          top=Q.front();
          Q.pop();
          if(top.k<0) continue;
          v[top.x][top.y][top.k]=1;
          for(int i=0;i<4;i++)
          {
           int nx=top.x+dx[i];
           int ny=top.y+dy[i];
           if(nx<0||nx>=n||ny<0||ny>=m) continue;
           if(a[nx][ny]==1&&top.k<1) continue;
           if(nx==n-1&&ny==m-1)
           {
               ans=min(ans,top.ans+1);
           }
           if(!v[nx][ny][top.k])
           {
               root.x=nx;
               root.y=ny;
               root.ans=top.ans+1;
               if(a[nx][ny]==1) root.k=top.k-1;
               else root.k=top.k;
               Q.push(root);
               v[nx][ny][top.k]=1;
           }
          }
      }
}
    int shortestPath(vector<vector<int>>& grid, int k) {
     K=k;
    n=grid.size();
    m=grid[0].size();
    if(n==1&&m==1) return 0;
    for(int i=0;i<n;i++)
    for(int j=0;j<m;j++)
    a[i][j]=grid[i][j];
    bfs();
    if(ans!=10000) return ans;
    return -1;
    return ans;
    }
};

多个原始点的搜索:
洛谷p1332
军团是一个n 行m 列的矩阵,每个单元是一个血色先锋军的成员。感染瘟疫的人,每过一个小时,就会向四周扩散瘟疫,直
到所有人全部感染上瘟疫。你已经掌握了感染源的位置,任务是算出血色先锋军的领主们感染瘟疫的时间,并且将它报告给
巫妖王,以便对血色先锋军进行一轮有针对性的围剿.
输入描述:
第一行:n,m,a,b;表示军团矩阵有n 行m 列。有 a 个感染源,b 为血色敢死队中领主的数量。
接下来a行:每行有两个整数x,y,表示感染源再第x行第y列。
接下来b行:每行两个整数x,y,表示领主的位置再第x行第y列。
输出描述:
第1行至第b行:每行一个整数,表示这个领主感染瘟疫的时间,输出顺序与输入顺序一致。
如果某个人的位置在感染原,那么他感染瘟疫的时间为0;

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int Max=5e2+20;
inline int read()
{
    int f=1,x=0;char ch;
    do{ch=getchar();if(ch=='-')f=-1;}
    while(ch<'0'||ch>'9');
    do{x=x*10+ch-'0';ch=getchar();}
    while(ch>='0'&&ch<='9');return x*f;
}
struct A
{
    int x,y,t;
}root,top;
int n,m;
int ans[Max][Max];
int p[100000][3];
bool v[Max][Max];
queue<A>Q;
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
void bfs()
{
 while(!Q.empty())
    {
        top=Q.front();
        Q.pop();
        v[top.x][top.y]=1;
        for(int i=0;i<4;i++)
        {
            int nx=top.x+dx[i];
            int ny=top.y+dy[i];
            int nt=top.t+1;
            if(nx<1||nx>n||ny<1||ny>m||v[nx][ny]) continue;
            ans[nx][ny]=nt;
            root.x=nx;
            root.y=ny;
            root.t=nt;
            Q.push(root);
            v[nx][ny]=1;
                  }
    }
}
int main()
{
   n=read(),m=read();
   int a=read(),b=read();
   for(int i=1;i<=a;i++)
   {
   root.x=read(),root.y=read();
    Q.push(root);//按顺序提前将搜索原点入队
    v[root.x][root.y]=1;//标记已经访问,防止别的搜索点访问搜索起点。
   }
   for(int i=1;i<=b;i++)
   {
       p[i][1]=read(),p[i][2]=read();//记录领主的位置
   }
   bfs();
   for(int i=1;i<=b;i++)
   {
       printf("%d\n",ans[p[i][1]][p[i][2]]);
   }
   return 0;
}
上一篇:自建C++工程代码调用OpenCV时使用CMakeLists.txt编译


下一篇:Aroma's Search CodeForces - 1292B