迷宫寻路：宽度优先搜索求最短路径

有一只小仓鼠身处在一个 N*M 迷宫之中，它现在想知道它最快能什么时候到达出口。迷宫是由 ‘ . ’ ‘ # ’  构成，’ . ’表示可以通行，‘#’表示墙壁，不能通行，现在小仓鼠在‘S’的位置上，问到出口’E’的最短时间是多少？

★数据输入

第一行两个整数 n,m(1<n,m<=1000)表示 n 行，m 列 接下来输入一个 n*m 的迷宫(只包含 ’ . ’ , ’ # ’, ’ S ’,’ E ’)

★数据输出

如果能到达则输出最短时间，否则输出-1

输入示例

输出示例

3 4

.... S.#.

.#.E

6

输入示例

输出示例

3 5

-1

..#..

#S#.E

...#.

解题思路：

宽度优先搜索。。。

#include <cstdio>

#include <queue>

using namespace std;

char maze[1005][1005];

int dis[1005][1005];

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

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

void BFS(int sx,int sy,int ex,int ey,int n,int m)

{

queue <pair <int,int> > q;

pair <int,int> p;

int x,y;

dis[sx][sy]=0;

p.first=sx,p.second=sy;

q.push(p);

while(!q.empty())

{

p=q.front();

x=p.first;

y=p.second;

q.pop();

for (int i=0;i<4;i++)

{

if (x+dx[i]<0 || x+dx[i]>=n ||y+dy[i]<0 || y+dy[i]>=m)

continue;

if (maze[x+dx[i]][y+dy[i]]!='#' && dis[x+dx[i]][y+dy[i]]==-1)

{

dis[x+dx[i]][y+dy[i]]=dis[x][y]+1;

p.first=x+dx[i],p.second=y+dy[i];

q.push(p);

}

if (x+dx[i]==ex&&y+dy[i]==ey)

return ;

}

}

}

int main()

{

int n,m,sx,sy,ex,ey;

scanf ("%d%d",&n,&m);

for (int i=0;i<n;i++)

{

scanf ("%s",maze[i]);

for (int j=0;j<m;j++)

{

dis[i][j]=-1;

if (maze[i][j]=='S')

{

sx=i;

sy=j;

}

else if (maze[i][j]=='E')

{

ex=i;

ey=j;

}

}

}

BFS(sx,sy,ex,ey,n,m);

printf ("%dn",dis[ex][ey]);

return 0;

}

相关知识

新手教程---动物行为学实验之「T迷宫」
​动物行为学迷宫知识点
【蓝桥杯】历届试题 青蛙跳杯子（广度优先搜索bfs）
蚁群算法+Dijkstra算法=二维路径规划,基于蚁群算法的机器人路径规划,matlab源码.rar资源
洛克王国游戏攻略：解析不同宠物的培养路径
2亿播放量的“仓鼠走迷宫”，成了YouTube上的财富密码
动物行为学实验：简易操作大小鼠迷宫套装
比较蚯蚓走迷宫和小鼠走迷宫的行为，可以说明（）
机械鼠鼠赛跑有什么好看的，怎么就成了男生减速带？
仓鼠迷宫

网址: 迷宫寻路：宽度优先搜索求最短路径 https://www.mcbbbk.com/newsview699898.html