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

bfs走迷宫

时间:2023-01-27 12:33:24浏览次数:34  
标签:end int 迷宫 st bfs 算法 && include

广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历算法这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS,属于一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。基本过程,BFS是从根节点开始,沿着树(图)的宽度遍历树(图)的节点。如果所有节点均被访问,则算法中止。一般用队列数据结构来辅助实现BFS算法。

 

来看一个例子 一、题目描述 给定一个 n × m 的二维整数数组,用来表示一个迷宫,数组中只包含 0或 1,其中 0表示可以走的路,1表示不可通过的墙壁。 最初,有一个人位于左上角 ( 1 , 1 )处,已知该人每次可以向上、下、左、右任意一个方向移动一个位置。 请问,该人从左上角移动至右下角 ( n , m )处,至少需要移动多少次。 数据保证 ( 1 , 1 ) 处和 ( n , m ) )处的数字为 0 ,且一定至少存在一条通路。 输入格式 第一行包含两个整数 n 和 m 。 接下来 n 行,每行包含 m 个整数(0 或 1 ),表示完整的二维数组迷宫。 输出格式 输出一个整数,表示从左上角移动至右下角的最少移动次数。 数据范围 1 ≤ n , m ≤ 100   0 0

 

#include <iostream>
#include<stdio.h>
#include<algorithm>
#include <queue>
#include<cstring>
using namespace std;
const int N = 1002;
//用于存储坐标
typedef pair<int,int> PII;
queue<int> stk;
int d[N][N];
char g[N][N];
int n,m,st_x,st_y,end_x,end_y;

void bfs()
{
    queue<PII> q;
    memset(d,-1,sizeof(d));
    
    //设置起点
    d[st_x-1][st_y-1] = 0;
    q.push({st_x-1,st_y-1});

    //四种可能的走法
    int dx[4] = {-1,0,1,0};
    int dy[4] = {0,1,0,-1};
    while (q.size())
    { 
        //取出一个点
        auto t = q.front();
        q.pop();
        //判断这个点周围是否存在可走的点,有就加入到数组
        for(int i = 0;i < 4;i++)
        {
            int x = t.first + dx[i],y = t.second + dy[i];
            if (x >=0 && x < n && y >=0 && y < n && g[x][y] == '.' && d[x][y] == -1)
            {
                //设置该点距离起点的距离
                d[x][y] = d[t.first][t.second] + 1;
                //把这个点入队
                q.push({x,y});
            }
        }
    }
    //未能到达这个点
    if (d[end_x - 1][end_y - 1] == -1)
    {
        cout << "-1" << endl;
    }
    else
    {
        cout << d[end_x - 1][end_y - 1];
    }
}
int main() {
    cin >> n >> m;
    cin >> st_x >> st_y >> end_x >> end_y;
    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < m;j++)
        {
            cin >> g[i][j];
        }
    }
    
    bfs();
    return 0;
}

 



标签:end,int,迷宫,st,bfs,算法,&&,include
From: https://www.cnblogs.com/polang19/p/17068760.html

相关文章

  • C++迷宫求解[2023-01-26]
    C++迷宫求解[2023-01-26](四)迷宫求解(****)1****、问题描述:以一个m*n的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个C++语言程序,对任意设定的迷宫,求出一条从入......
  • 迷宫回溯问题分析
    问题:迷宫为8x8的二位数组,其中0为道路,1为墙,人如何在起点和终点之前获取一条可达路径。 自定义的概念: 当前位置:人当前所在的位置,通过当前位置不断变动形成一条路径。......
  • 迷宫
    题目描述下图给出了一个迷宫的平面图,其中标记为 1 的为障碍,标记为 0 的为可以通行的地方。010000000100001001110000迷宫的入口为左上角,出口为右下角,在迷宫中,......
  • 【BFS】LeetCode 417. 太平洋大西洋水流问题
    题目链接417.太平洋大西洋水流问题思路问题可以转换成从四个边界出发,能和内部哪些点连通。因为涉及到两个可达性问题,所以用两个boolean类型矩阵分别记录一个点到太......
  • 【BFS】LeetCode 542. 01 矩阵
    题目链接542.01矩阵思路题目让求1到0的距离,其实可以转换成求0到1的距离,将所有的0作为源结点放入队列进行BFS。BFS本质上就是从源点开始的搜索算法,本题只不过是所有的......
  • 【BFS】LeetCode 1091. 二进制矩阵中的最短路径
    题目链接1091.二进制矩阵中的最短路径思路BFS找最短路模板题代码classSolution{publicintshortestPathBinaryMatrix(int[][]grid){if(grid[0][......
  • 【Java】蚂蚁迷宫问题
    packagecom;publicclassMiGong{publicstaticvoidmain(String[]args){//思路//1、先创建迷宫,用二维数组表示intmap[][]=newint[8][7];......
  • D. Friendly Spiders(bfs最短路径、质数虚点建图)
    题意:给一个长度为n的数组a,数组中两两不互质的数可以建一条边,即$gcd(a[i],a[j])≠1$,i,j之间存在伊奥无向边问s到t的最短路径是多长,并输出题解根据唯一分解......
  • 【BFS】LeetCode 133. 克隆图
    题目链接133.克隆图思路代码classSolution{publicNodecloneGraph(Nodenode){if(node==null){returnnode;}H......
  • 迷宫机器人最短路径使用tkinter绘制
    起因我想要写一个玩家和机器对战的迷宫游戏。这个项目我没有写完,我实现了最短机器人路径并绘制在tkinter上,以及玩家移动的功能。更多的关于GUI的设计太花时间了我没有写完......