首页 > 代码库 > 迷宫问题 模拟队列 广度优先搜索
迷宫问题 模拟队列 广度优先搜索
Description
定义一个二维数组：
它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
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表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
Input
一个5 × 5的二维数组，表示一个迷宫。数据保证有唯一解。
Output
左上角到右下角的最短路径，格式如样例所示。
Sample Input
0 1 0 0 00 1 0 1 00 0 0 0 00 1 1 1 00 0 0 1 0
Sample Output
(0, 0)(1, 0)(2, 0)(2, 1)(2, 2)(2, 3)(2, 4)(3, 4)(4, 4)
#include <cstdio>#include <cmath>#include <cstring>#include <ctime>#include <iostream>#include <algorithm>#include <set>#include <vector>#include <sstream>#include <queue>#include <typeinfo>#include <fstream>typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 100const int inf=0x7fffffff; //无限大struct dota{ int x; int y; int pre;} haha[1000];int dx[4]={1,-1,0,0};int dy[4]={0,0,1,-1};//int dp[10][10];int vis[50][50];void print(int x){ if(haha[x].pre!=-1) { print(haha[x].pre); printf("(%d, %d)\n",haha[x].x,haha[x].y); }}void bfs(int x,int y){ haha[0].x=x; haha[0].y=y; haha[0].pre=-1; int start=0; int fina=1; int m=1; while(start<fina) { for(int i=0;i<4;i++) { int a=haha[start].x+dx[i]; int b=haha[start].y+dy[i]; if(a<0||a>4) continue; if(b<0||b>4) continue; if(vis[a][b]==1) continue; fina++; vis[a][b]=1; haha[m].x=a; haha[m].y=b; haha[m++].pre=start; if(a==4&&b==4) { print(start); } } start++; }}int main(){ for(int i=0;i<5;i++) for(int j=0;j<5;j++) { cin>>vis[i][j]; } printf("(0, 0)\n"); bfs(0,0); printf("(4, 4)\n"); return 0;}
迷宫问题 模拟队列 广度优先搜索
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。