当前位置：首页 > news >正文

搜索-BFS

news 来源：原创 2025/7/5 16:52:20

马上蓝桥杯了，最近刷了广搜，感觉挺有意思的，广搜题类型都差不多，模板也一样，大家写的时候可以直接套模板

这里给大家讲一个比较经典的广搜题-迷宫

题目问问能否走到 (n,m) 位置，假设最后一个点是我们的（n,m) 点

那我们如何判断是否可以走到我们的（n,m）点呢？

题目给我们的起点是（1，1），然后对应的数组下标就是（0，0），（下面我们说的坐标都是我们的数组下标）首先我们定义我们的一个二维数组maze来存储我们的迷宫，然后现在从（0，0）坐标开始，我们需要定义一个队列来存储我们的可用的坐标，遍历我们的坐标，然后这里我们有四个方向可以走，上下左右，就是说当我们达到该坐标的时候，需要遍历上下左右四个方向，然后将可以用的坐标进行存储到我们的队列当中

但是通过上图可以看到，当向上和向左的时候，我们的坐标越界了，没有意义，所以我们不需要处理这两个坐标，然后向右，我们发现是面墙，因为题目说" # "是一个墙，这个坐标是不能使用的，所以这里我们遍历到该坐标的时候需要一个判断看该坐标是不是" . " ，然后遍历下面，发现既没有越界，也不是墙，所以我们就将该坐标（1，0）添加到我们的队列里面，然后（0，0）坐标使用过了，我们就使用pop()方法将它删除，因为我们遍历所有可添加的坐标，使用需要将不用的坐标进行删除

通过第一次（0，0）坐标的四个方向遍历，我们已经（1，0）坐标添加上去，然后继续进行遍历~

遍历完成之后添加我们的（2，0），但是当我们遍历上面的点时，我们发现有问题，因为我们已经走过（0，0）点了，使用我们还需要一个数组dist，来储存我们走过的坐标....，如果走过，就让该坐标当下的值变成1，0表示没有走过，1表示走过，如果没有走过我们才将坐标添加上去，依次类推，直到找到我们的（n,m）点，然后进行输出，如果遍历完还没有找到，就输出No

定义：

 char maze[N][N];//迷宫int dist[N][N];//路径queue<pair<int,int> > q;//定义队列

初始化：

  memset(dist,0,sizeof(dist));dist[0][0]=1;//1表示走过，0表示没有走过q.push({0,0});//初始化队列

定义上下左右移动数组：

   int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};

遍历队列坐标：（广搜模板）

    while(!q.empty()){auto[x,y]=q.front();q.pop();// 遍历上下左右四个方向for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];//判断是否到达了该坐标if(nx==n-1&&ny==m-1){cout<<"Yes";return 0;}//判断是否可以添加该坐标if(nx>=0&&nx<=n&&ny>=0&&ny<=m&&maze[nx][ny]=='.'&&dist[nx][ny]==0){dist[nx][ny]=1;q.push({nx,ny});}}}

下面是代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=100;
char maze[N][N];//迷宫
int dist[N][N];//路径
queue<pair<int,int> > q;
int main(){int n,m;cin>>n>>m;dist[0][0]=1;//1表示走过，0表示没有走过q.push({0,0});//初始化队列memset(dist,0,sizeof(dist));for(int i=0;i<n;i++){for(int j=0;j<m;j++){cin>>maze[i][j];}}//定义上下左右移动数组int dx[4]={-1,1,0,0};int dy[4]={0,0,-1,1};while(!q.empty()){auto[x,y]=q.front();q.pop();// 遍历上下左右四个方向for(int i=0;i<4;i++){int nx=x+dx[i];int ny=y+dy[i];if(nx==n-1&&ny==m-1){cout<<"Yes";return 0;}if(nx>=0&&nx<=n&&ny>=0&&ny<=m&&maze[nx][ny]=='.'&&dist[nx][ny]==0){dist[nx][ny]=1;q.push({nx,ny});}}}cout<<"No";return 0;
}

如果大家听懂了，可以写一下P1443 马的遍历 - 洛谷题来检测一下，一样的类型

相关文章：