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。

相关文章

hdu1254（嵌套bfs，两次bfs）

hdu1254（嵌套bfs，两次bfs）

/*第一次做这种题感觉很有压力，思路还是有点混乱，总是wa，改了好多次才ac的思路：把箱子的移动当做第一层bfs，队列节点要用到当前箱子坐标（x，y），走的次数step，当前人的weizhi（man_x，man_y），要判断人能否将箱子推到某点时要嵌套第二层bfs（人的移动）；代码如下：
阅读更多...
poj 2195 bfs+有流量限制的最小费用流

poj 2195 bfs+有流量限制的最小费用流

题意： 给一张n * m（100 * 100）的图，图中” . " 代表空地， “ M ” 代表人， “ H ” 代表家。 现在，要你安排每个人从他所在的地方移动到家里，每移动一格的消耗是1，求最小的消耗。 人可以移动到家的那一格但是不进去。 解析： 先用bfs搞出每个M与每个H的距离。 然后就是网络流的建图过程了，先抽象出源点s和汇点t。 令源点与每个人相连，容量为1，费用为
阅读更多...
POJ 3057 最大二分匹配+bfs + 二分

POJ 3057 最大二分匹配+bfs + 二分

SampleInput35 5XXDXXX...XD...XX...DXXXXX5 12XXXXXXXXXXXXX..........DX.XXXXXXXXXXX..........XXXXXXXXXXXXX5 5XDXXXX.X.DXX.XXD.X.XXXXDXSampleOutput321impossible
阅读更多...
深度优先（DFS）和广度优先（BFS）——算法

深度优先（DFS）和广度优先（BFS）——算法

深度优先 深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。 沿着树的深度遍历树的节点，尽可能深的搜索树的分支，当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访
阅读更多...
nyoj306(走迷宫)

nyoj306(走迷宫)

走迷宫 时间限制： 1000 ms  |  内存限制： 65535 KB 难度：5 描述 Dr.Kong设计的机器人卡多非常爱玩，它常常偷偷跑出实验室，在某个游乐场玩之不疲。这天卡多又跑出来了，在SJTL游乐场玩个不停，坐完碰碰车，又玩滑滑梯，这时卡多又走入一个迷宫。整个迷宫是用一个N * N的方阵给出，方阵中单元格中填充了一个整数，表示走到这个位置的难度。 这个迷宫可以向上走，向
阅读更多...
双头BFS

双头BFS

牛客月赛100 D题，过了80%数据，调了一下午。。。烦死了。。。 还是没调试出来，别人的代码用5维的距离的更新有滞后性，要在遍历之前要去重。。。 #include<bits/stdc++.h>using namespace std;const int N=2e3+10;char g[N][N];int dis[N][N],d1[N][N];int n,m,sx,sy;int dx
阅读更多...
Knight Moves -uva 简单的BFS遍历

Knight Moves -uva 简单的BFS遍历

昨天刚学了BFS的遍历，在uva上找了个题敲了出来，感觉还不错，最近敲代码挺有手感的，希望这种状态保持下去 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<string.h>#define MAX_SIZE 10 + 5#define LEN 100 + 10using namespace std;in
阅读更多...
【CF】D. Arthur and Walls（BFS + 贪心）

【CF】D. Arthur and Walls（BFS + 贪心）

D题 解题思路就是每次检查2X2的方格里是否只有一个‘*’，如果有的话这个*就需要变成‘.’，利用BFS进行遍历，入队的要求是这个点为. 一开始将所有的'.'全部加入队列，如果碰到一个'*'变成'.'就入队，判断的时候从4个方向就行判断 题目链接：http://codeforces.com/contest/525/problem/D #include<cstdio>#include<
阅读更多...
hdu2717(裸bfs广搜)

hdu2717(裸bfs广搜)

Catch That Cow Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 7304 Accepted Submission(s): 2308 题目链接： http://acm.hdu.edu.cn/showproblem.
阅读更多...
Codeforces#295(Div.2)A、B(模拟+BFS)

Codeforces#295(Div.2)A、B(模拟+BFS)

解题报告链接：点击打开链接 C. 题目链接：点击打开链接 解题思路： 对于给定的字符串，取出现次数最多的字母（可以同时有多个）。由这些字母组成长度为n的字符串，求有多少种组合。最后用数学知识即可。 完整代码： #include <algorithm>#include <iostream>#include <cstring>#include <climits>
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2