首页 > 其他分享 >bfs走迷宫

bfs走迷宫

时间:2023-03-16 21:35:21浏览次数:36  
标签:PII int 迷宫 bfs second && include

 

 #include<iostream>

#include<cstring>

#include<queue>

const int N=110;

int n,m;

typedef pair<int,int> PII;

int g[N][N];//存图

int d[N][N];//记录距离

PII q[N*N];//队列存放走的路线

 

int bfs(){

 

queue <PII> q;

q[0]={0,0};//起始位置

memset(d,-1,sizeof d);//初始化d为-1

d[0][0]=0;//源点到起点的位置

 

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

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

while(!q.empty()){

auto t=q.front();

q.pop();

for(int i=0;i<4;i++){//记录分别从四个方向走

int x=t.first+dx[i];

int y=t.second+dy[i];

if(x>=0&&x<n&&y>=0&&y<m&&g[x][y]=0&&d[x][y]==-1){

d[x][y]=d[t.first][t.second]+1;//距离+1,消除没走过的状态

q[++t]={x,y};//把点加进队列

}

}

}

return d[n-1][m-1];

}

int main(){

cin>>n>>m;

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

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

cin>>g[i][j];//先输入地图

 

cout<<bfs()<<endl;

}

 

标签:PII,int,迷宫,bfs,second,&&,include
From: https://www.cnblogs.com/chenxinyue/p/17224210.html

相关文章

  • 基于形态学处理算法的迷宫路线搜索matlab仿真
    1.算法描述形态学是图像处理中应用最为广泛的技术之一,主要用于从图像中提取对表达和描绘区域形状有意义的图像分量,使后续的识别工作能够抓住目标对象最为本质的形状特征,如......
  • 基于形态学处理算法的迷宫路线搜索matlab仿真
    1.算法描述       形态学是图像处理中应用最为广泛的技术之一,主要用于从图像中提取对表达和描绘区域形状有意义的图像分量,使后续的识别工作能够抓住目标对象最为本......
  • 迷宫问题
    (啊哈哈哈鸡汤来咯)设有一个N×N(2<=N<=10)方格的迷宫,入口和出口分别在左上角和右上角。迷宫格子中分别放0和1,0表示可通,1表示不能,入口和出口处肯定是0.迷宫走的规则如下所......
  • n-皇后问题(bfs)
        #include<iostream>usingnamespacestd;constintN=20;//N*N两倍intn;boolcol[N],dg[N],udg[N];//同一列,对角线,反对角线(标记一下是否可以走)charg[......
  • # 909 -「java」一维数组展开+ BFS解决 -蛇梯棋- 最短步进次数 的详细思路
    Tags:中等数组BFSjava 题目链接:909.蛇梯棋 注意事项[题目中的坑]:【"S形"的概念】:题目开头举例的N*N的数组,其内标示的1~N²数字,指代的是......
  • 2020 年百度之星·程序设计大赛 - 初赛一 Civilization BFS广搜
    problemCivilizationAccepts:619Submissions:2182TimeLimit:6000/3000MS(Java/Others)MemoryLimit:32768/32768K(Java/Others)ProblemDescription这是一个......
  • dfs入门,一个简单的迷宫问题
    AcWing走迷宫问题给定一个 n×m 的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0 表示可以走的路,1 表示不可通过的墙壁。最初,有一个人位于左上角 (1,1......
  • 迷宫危机“分支语句”
    今日份学习“分支语句”本文简介:该篇文章介绍分支语句,主要讲解其用法和注意事项,让我们使用该语句上有更好的概念(不再犯选择困难症......
  • AC.844 走迷宫
     #include<iostream>#include<queue>#include<utility>//pair容器的头文件#include<cstring>//memsetusingnamespacestd;constintN=1e2+7;intn,m;intg[......
  • bfs: 通过利用其它点到出发点的距离 来表示bfs的层数
    题目:微博被称为中文版的Twitter。微博上的用户既可能有很多关注者,也可能关注很多其他用户。因此,形成了一种基于这些关注关系的社交网络。当用户在微博上发布帖子时,他/......