BFS【2】迷宫

2024-06-22 06:29
文章标签 bfs 迷宫

本文主要是介绍BFS【2】迷宫，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

迷宫

走到右下角最短路径长度

走到右下角最短路径

跨步迷宫

 

迷宫

走到右下角最短路径长度

我是和上一篇一样，创建一个队列，不过while 里面判责是queue非空，否则会死循环万一是死路的话。

也是要判断不要重复入队。

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=102,maxn=10;int n,m;
int W[N][N];
int row[]={0,0,1,-1};
int col[]={1,-1,0,0};
struct point
{int x;int y;} p;point pre[N][N];
queue<point> q;
int bushu[N][N];
bool inq[N][N]={0};int T=0;
int bfs()
{p.x=0;p.y=0;q.push(p);//printf("?");inq[0][0]=1;while(!q.empty()){int c=q.size();	//	printf("?%d?",c);for(int i=0;i<c;i++){	//	printf("!*");int x1=q.front().x;int y1=q.front().y;
//printf("%d%d%d\n",x2,y2,W[x2][y2]);for(int j=0;j<4;j++)//艹，一开始写的i<4，找死了。 {//printf("j=%d\n",j);int x2=x1+row[j];int y2=y1+col[j];//printf("%d%d%d\n",x2,y2,W[x2][y2]);if(x2>=0 && y2>=0 && x2<n && y2<m && !W[x2][y2] && !inq[x2][y2]) {p.x=x2;p.y=y2;q.push(p);inq[x2][y2]=1;//printf("x2y2$%d %d %d=\n",x2,y2,T);if(!bushu[x2][y2]){bushu[x2][y2]=T+1;pre[x2][y2]=q.front();}if(x2==n-1 && y2==m-1){ //printf("#x2=%d y2=%d,T=%d\n#",x2,y2,T);return T+1;  } }}q.pop();}T++;//printf("T=%d\n!",T);}
return -1;	
}int main()
{//D[0][0]=1;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{scanf("%d",&W[i][j]);}
//int ans=0;
//for(int i=0;i<n;i++)
//{for(int j=0;j<m;j++)
//{
//	if(can(i,j))
//	{//printf("^");
//	bfs(i,j);ans++;//printf("\n-%d%d-\n",i,j);
//	}
//}
printf("%d",bfs());//for(int i=0;i<n;i++)
//for(int j=0;j<m;j++)
//printf("%d " ,bushu[i][j]);
//printf("%d",bushu[n-1][m-1]);
}

走到右下角最短路径

我用了一个先进后出的vector<point>,point是我自己造的结构体，每个点记录上一个点的point值，类似于动态规划的局部最优。

 

tips：如何取出vector的末尾元素？

声明：vector<T> vec;

 

方法一： return vec.at(vec.size()-1);

 

方法二： return vec.back();

 

方法三： return vec.end()-1; 注意：end指向末尾元素的下一个元素。

 

方法四： return vec.rbegin();

 

方法五： return std::end(vec)-1;

 

方法六： return std::rbegin(vec);

 

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=102,maxn=10;int n,m;
int W[N][N];
int row[]={0,0,1,-1};
int col[]={1,-1,0,0};
struct point
{int x;int y;} p;point pre[N][N];
queue<point> q;
int bushu[N][N];
bool inq[N][N]={0};int T=0;
void bfs()
{p.x=0;p.y=0;q.push(p);//printf("?");inq[0][0]=1;while(!q.empty()){int c=q.size();	//	printf("?%d?",c);for(int i=0;i<c;i++){	//	printf("!*");int x1=q.front().x;int y1=q.front().y;
//printf("%d%d%d\n",x2,y2,W[x2][y2]);for(int j=0;j<4;j++)//艹，一开始写的i<4，找死了。 {//printf("j=%d\n",j);int x2=x1+row[j];int y2=y1+col[j];//printf("%d%d%d\n",x2,y2,W[x2][y2]);if(x2>=0 && y2>=0 && x2<n && y2<m && !W[x2][y2] && !inq[x2][y2]) {p.x=x2;p.y=y2;q.push(p);inq[x2][y2]=1;//printf("x2y2$%d %d %d=\n",x2,y2,T);if(!bushu[x2][y2]){bushu[x2][y2]=T+1;pre[x2][y2]=q.front();}if(x2==n-1 && y2==m-1){ //printf("#x2=%d y2=%d,T=%d\n#",x2,y2,T);return ;  } }}q.pop();}T++;//printf("T=%d\n!",T);}
return ;	
}int main()
{//D[0][0]=1;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{scanf("%d",&W[i][j]);}
//int ans=0;
//for(int i=0;i<n;i++)
//{for(int j=0;j<m;j++)
//{
//	if(can(i,j))
//	{//printf("^");
//	bfs(i,j);ans++;//printf("\n-%d%d-\n",i,j);
//	}
//}
//printf("%d",bfs());
bfs();
point p0;
vector<point> path;
p0.x=n-1;p0.y=m-1;
path.push_back(p0);
while (p0.x || p0.y)
{int x=p0.x;int y=p0.y;p0.x=pre[x][y].x;p0.y=pre[x][y].y;
//	printf("_%d%d_\n",p0.x,p0.y);path.push_back(p0);
}while(!path.empty())
{printf("%d %d",path.back().x+1,path.back().y+1);path.pop_back();if(!path.empty()) printf("\n");
}//for(int i=0;i<n;i++)
//for(int j=0;j<m;j++)
//printf("%d " ,bushu[i][j]);
//printf("%d",bushu[n-1][m-1]);
}

答案用的是递归print path

void printPath(Position p) {Position prePosition = pre[p.first][p.second];if (prePosition == Position(-1, -1)) {printf("%d %d\n", p.first + 1, p.second + 1);return;}printPath(prePosition);printf("%d %d\n", p.first + 1, p.second + 1);
}

跨步迷宫

可以走两步，没什么好说的，加上取中点验证 ，但是我把后面一段放到if'外面了，检查了半天，ε=(´ο｀*)))唉

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <cstring>
#include <queue>
using namespace std;
const int N=102,maxn=10;int n,m;
int W[N][N];
int row[]={0,0,0,0,1,-1,2,-2};
int col[]={1,-1,2,-2,0,0,0,0};
struct point
{int x;int y;} p;point pre[N][N];
queue<point> q;
int bushu[N][N];
bool inq[N][N]={0};int T=0;
int bfs()
{p.x=0;p.y=0;q.push(p);//printf("?");inq[0][0]=1;while(!q.empty()){int c=q.size();	//	printf("?%d?",c);for(int i=0;i<c;i++){	//	printf("!*");int x1=q.front().x;int y1=q.front().y;
//printf("%d%d%d\n",x2,y2,W[x2][y2]);for(int j=0;j<8;j++)//艹，一开始写的i<4，找死了。 {//printf("j=%d\n",j);int x2=x1+row[j];int y2=y1+col[j];//printf("%d%d%d\n",x2,y2,W[x2][y2]);if(x2>=0 && y2>=0 && x2<n && y2<m && !W[x2][y2] && !inq[x2][y2]) {int flag=1;if(abs(row[j])==2) if(W[(x2+x1)/2][y2]) flag=0;if(abs(col[j])==2)  if(W[x2][(y2+y1)/2]) flag=0;//		printf("%d %d %d %d %d %d %d\n\n",x2,y2,x2,y1,W[(x2+x1)/2][y2],W[x2][(y2+y1)/2],flag);if(flag){			p.x=x2;p.y=y2;q.push(p);inq[x2][y2]=1;if(!bushu[x2][y2]){bushu[x2][y2]=T+1;pre[x2][y2]=q.front();}if(x2==n-1 && y2==m-1){ //printf("#x2=%d y2=%d,T=%d\n#",x2,y2,T);return T+1;  } }//printf("x2y2$%d %d %d=\n",x2,y2,T);}}q.pop();}T++;//printf("T=%d\n!",T);}
return -1;	
}int main()
{//D[0][0]=1;
scanf("%d %d",&n,&m);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{scanf("%d",&W[i][j]);}
//int ans=0;
//for(int i=0;i<n;i++)
//{for(int j=0;j<m;j++)
//{
//	if(can(i,j))
//	{//printf("^");
//	bfs(i,j);ans++;//printf("\n-%d%d-\n",i,j);
//	}
//}
printf("%d",bfs());
//bfs();printf("%d",bushu[n-1][m-1]);
point p0;
vector<point> path;
p0.x=n-1;p0.y=m-1;
//path.push_back(p0);
//while (p0.x || p0.y)
//{
//	int x=p0.x;int y=p0.y;
//	p0.x=pre[x][y].x;p0.y=pre[x][y].y;printf("_%d%d_\n",p0.x,p0.y);
//	path.push_back(p0);
//}
//
//
//while(!path.empty())
//{
//	printf("%d %d",path.back().x+1,path.back().y+1);
//	path.pop_back();
//	if(!path.empty()) printf("\n");
//}//for(int i=0;i<n;i++)
//for(int j=0;j<m;j++)
//printf("%d " ,bushu[i][j]);
//printf("%d",bushu[n-1][m-1]);
}

 

还有走马字的，懒得写了，就是判断条件改来改去的。

 

这篇关于BFS【2】迷宫的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1083532。

相关文章

多源 BFS

多源 BFS

例题一 解法（bfs）（多个源头的最短路问题） 算法思路： 对于求的最终结果，我们有两种⽅式： • 第⼀种⽅式：从每⼀个 1 开始，然后通过层序遍历找到离它最近的 0 。 这⼀种⽅式，我们会以所有的 1 起点，来⼀次层序遍历，势必会遍历到很多重复的点。并且如果 矩阵中只有⼀个 0 的话，每⼀次层序遍历都要遍历很多层，时间复
阅读更多...
BFS：解决多源最短路问题

BFS：解决多源最短路问题

文章目录 什么是多源最短路问题？1.矩阵2.飞地的数量3.地图的最高点4.地图分析总结 什么是多源最短路问题？ 多源最短路问题（Multi-Source Shortest Path Problem，MSSP）是图论中的一个经典问题，它的目标是在给定图中找到从多个源点到所有其他顶点的最短路径。这个问题可以视为单源最短路问题（Single-Source Shortest Pa
阅读更多...
[AIGC] 宽度优先搜索(BFS) 讲解以及在 LeetCode 题中的应用

[AIGC] 宽度优先搜索(BFS) 讲解以及在 LeetCode 题中的应用

宽度优先搜索（Breadth-First Search，简称 BFS）是一种用于图或树结构的遍历算法。它以广度方向进行搜索，首先访问根节点，然后访问所有相邻的节点，然后再通过它们的邻居一直进行下去，直到所有的节点都被访问过。 文章目录 BFS 的工作过程BFS 在 LeetCode 中的应用 BFS 的工作过程 BFS 从图的某一节点（称为“源”节点）开始，访问可能
阅读更多...
BFS 解决最短路问题

BFS 解决最短路问题

例题一 解法（bfs 求最短路）： 算法思路： 利⽤层序遍历来解决迷宫问题，是最经典的做法。我们可以从起点开始层序遍历，并且在遍历的过程中记录当前遍历的层数。这样就能在找到出⼝的时候，得到起点到出⼝的最短距离。 例题二 解法： 算法思路： 如果将「每次字符串的变换」抽象成图中的「两个顶点和⼀条边」的话，问题就变成了「边权为
阅读更多...
洛谷 P1141 01迷宫 (dfs解决)

洛谷 P1141 01迷宫 (dfs解决)

题目描述 有一个仅由数字 0 与 1 组成的 n×n 格迷宫。若你位于一格 0 上，那么你可以移动到相邻 4 格中的某一格 1 上，同样若你位于一格 1 上，那么你可以移动到相邻 4 格中的某一格 0 上。 你的任务是：对于给定的迷宫，询问从某一格开始能移动到多少个格子（包含自身）。 输入格式 第一行为两个正整数 𝑛,𝑚。 下面 𝑛 行，每行 𝑛 个字符，字符只可能是 0 或者
阅读更多...
DFS走迷宫（懒猫老师C++完整版）

DFS走迷宫（懒猫老师C++完整版）

DFS走迷宫的C++完整版 知识储备一：普通动态二维数组的构造二：栈的构造三：栈的逆序遍历 Main文件代码 该版本代码是配合 懒猫老师用DFS走迷宫视频 基于C++基础所写的完整版（实现了栈逆序遍历），适合小白系统性的学习和复习知识点，只要将下文.h和.cpp和main文件所展示的代码结合起来就是个完整的代码。 知识储备 一：普通动态二维数组的构造 二维数组中不同行的内
阅读更多...
BFS:FloodFill算法

BFS:FloodFill算法

文章目录 FloodFill算法简介1.图像渲染2.岛屿数量3.岛屿的最大面积4.被围绕的区域总结 FloodFill算法简介 Flood Fill算法是一种用于确定与某个给定节点相连的区域的算法，常用于计算机图形学和图像处理。该算法可以用于诸如填充多边形、检测连通区域等任务。Flood Fill算法有多种实现方式，其中最常见的是递归方法和使用栈或队列的迭代方法。 基本
阅读更多...
[状态压缩 广搜BFS]Saving Tang Monk

[状态压缩 广搜BFS]Saving Tang Monk

描述 《Journey to the West》(also 《Monkey》) is one of the Four Great Classical Novels of Chinese literature. It was written by Wu Cheng'en during the Ming Dynasty. In this novel, Monkey King Sun Wukong,
阅读更多...
[深度优先搜索DFS]迷宫问题

[深度优先搜索DFS]迷宫问题

描述 定义一个二维数组： int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 0, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,}; 它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。 输入 一个5 × 5的二维数组，表示一个迷宫。数
阅读更多...
【LeetCode】 Surrounded Regions （BFS DFS）

【LeetCode】 Surrounded Regions （BFS DFS）

题目：Surrounded Regions 广搜和深搜都能解决，但是LeetCode上使用深搜时会栈溢出 DFS: <span style="font-size:18px;">/*LeetCode Surrounded Regions* 题目：给定一个字符数组，由'X'和'O'组成，找到所有被x包围的o并将其替换为x* 思路：只要替换被包围的o就行，如果有一个o是边界或者上下左右中有一个
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2