蓝桥杯走迷宫BFS算法

JAY.LIN 收录于算法竞赛题目超详细解析

2025-03-09 约 900 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146126076

蓝桥杯—走迷宫(BFS算法)

题目描述

给定一个N×M 的网格迷宫 G。G 的每个格子要么是道路，要么是障碍物（道路用 11表示，障碍物用 0 表示）。

已知迷宫的入口位置为 (x1,y1)，出口位置为 (x2,y2)。问从入口走到出口，最少要走多少个格子。

输入描述

输入第 11 行包含两个正整数 N,M，分别表示迷宫的大小。

接下来输入一个 𝑁×𝑀N×M 的矩阵。若 Gi,j=1 表示其为道路，否则表示其为障碍物。

最后一行输入四个整数 𝑥1,𝑦1,𝑥2,𝑦2表示入口的位置和出口的位置。

1≤N,M≤102，0≤Gi,j≤1，1≤x1,x2≤N，1≤y1,y2≤M。

输出描述

输出仅一行，包含一个整数表示答案。

若无法从入口到出口，则输出 −1；

输入输出样例

示例 1

输入

输出

运行限制

最大运行时间：1s
最大运行内存: 128M

代码为：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define  x first
#define  y second
using namespace std;
typedef pair<int,int> PII;
const int N=1e2+10;
int n,m;
int x2,y2;//出口的位置
int g[N][N];//存储地图
int dist[N][N];//每个点到起点的距离 
queue<PII> q;//存坐标
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int bfs(int x1,int y1)
{
  memset(dist,-1,sizeof dist);//初始都为-1
  q.push({x1,y1});
  dist[x1][y1]=0;

  while(!q.empty()){
    auto Top=q.front();//取出对头
    q.pop();//弹出对头

    for(int i=0;i<4;i++)
    {
    int a=Top.x+dx[i];
    int b=Top.y+dy[i];//入口的位置的下一个位置
    if(a<0||a>n||b<0||b>m) continue;//越界
    if(g[a][b]!=1) continue;//不是道路
   if(dist[a][b]>1) continue;
    q.push({a,b});

    dist[a][b]=dist[Top.x][Top.y]+1;

    if(a==x2&&b==y2) return dist[x2][y2];

    }
  }
 return -1;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x1,y1;//入口的位置
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    cin>>g[i][j];
  }
  cin>>x1>>y1>>x2>>y2;
  int res=bfs(x1,y1);
  cout<<res<<'\n';
  return 0;
}

优化后的代码（运行时间1ms）：

#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define  x first
#define  y second
using namespace std;
typedef pair<int,int> PII;
const int N=1e2+10;
int n,m;
int x2,y2;//出口的位置
int g[N][N];//存储地图
int dist[N][N];//每个点到起点的距离 
queue<PII> q;//存坐标
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

int bfs(int x1,int y1)
{
  memset(dist,-1,sizeof dist);//初始都为-1
  q.push({x1,y1});
  dist[x1][y1]=0;

  while(!q.empty()){
    auto Top=q.front();//取出对头
    q.pop();//弹出对头

    for(int i=0;i<4;i++)
    {
    int a=Top.x+dx[i];
    int b=Top.y+dy[i];//入口的位置的下一个位置
    if(a<0||a>n||b<0||b>m) continue;//越界
    if(g[a][b]!=1) continue;//不是道路
   if(dist[a][b]>1) continue;
    q.push({a,b});

    dist[a][b]=dist[Top.x][Top.y]+1;

    if(a==x2&&b==y2) return dist[a][b];

    }
  }
 return -1;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int x1,y1;//入口的位置
  cin>>n>>m;
  for(int i=1;i<=n;i++)
  {
    for(int j=1;j<=m;j++)
    cin>>g[i][j];
  }
  cin>>x1>>y1>>x2>>y2;
  int res=bfs(x1,y1);
  cout<<res<<'\n';
  return 0;
}