迷宫最短路径(dfs,bfs)-程序员宅基地

技术标签: dfs  笔记  数据结构  bfs  

迷宫最短路径

题目描述
设计一个算法找一条从迷宫入口到出口的最短路径。
输入
迷宫的行和列m n

迷宫的布局

输出
最短路径

样例输入
6 8
0 1 1 1 0 1 1 1
1 0 1 0 1 0 1 0
0 1 0 0 1 1 1 1
0 1 1 1 0 0 1 1
1 0 0 1 1 0 0 0
0 1 1 0 0 1 1 0
样例输出
(6,8)(5,7)(4,6) (4,5)(3,4) (3,3) (2,2)(1,1)

这是一道比较简单练习广搜的题,然后我刚开始写这题时并没有学习广搜,只是初步接触了一下深搜,故一开始使用深搜,显然,时间超限,后面学习广搜才成功解决,然后我把深搜和广搜的代码都写一下,正好练习一下。首先贴出深搜代码。

#include <iostream>
#include<stdio.h>
using namespace std;
int m,n,Min=98769954;
int a[1005][1005];
int vis[1005][1005];
typedef struct point
{
    
    int x3,y3;
} Point;
Point path[100010];
Point shortest_path[10010];
int moves[8][2]= {
    {
    0,-1},{
    -1,-1},{
    -1,0},{
    -1,1},{
    0,1},{
    1,1},{
    1,0},{
    1,-1}};
void dfs(int x,int y,int step)
{
    
    if(x==m&&y==n)
    {
    
        if(step<Min)
        {
    
            Min=step;
            for(int i=0;i<step;i++)
            {
    
                shortest_path[i]=path[i];
            }
        }
        return ;
    }
    for(int i=0; i<8; i++)
    {
    
        int nx=x+moves[i][0];
        int ny=y+moves[i][1];
        if(nx<1||nx>m||ny<1||ny>n) continue;
        if(vis[nx][ny]==0&&a[nx][ny]==0)
        {
    
            vis[nx][ny]=1;
            path[step].x3=nx;
            path[step].y3=ny;
            dfs(nx,ny,step+1);
            vis[nx][ny]=0;
        }
    }
    return ;
}
int main()
{
    
    scanf("%d%d",&m,&n);
    for(int i=1; i<=m; i++)
        for(int j=1; j<=n; j++)
        {
    
            scanf("%d",&a[i][j]);
        }
    vis[1][1]=1;
    path[0]={
    1,1};
    dfs(1,1,1);
    for(int i=Min-1;i>=0;i--)
    {
    
        printf("(%d,%d) ",shortest_path[i].x3,shortest_path[i].y3);
    }
    return 0;
}

这个深搜代码,比较容易写出来,就是时间复杂性高。提交的时候只能过一部分数据,后面一部分时间就超限了。
接下来是广搜代码

#include <iostream>
#include<stdio.h>
#include<queue>

using namespace std;
typedef pair<int,int> PI;
int maze[1005][1005];
int vis[1005][1005];
PI pre[1005][1005];
int moves[8][2]= {
    {
    0,-1},{
    -1,-1},{
    -1,0},{
    -1,1},{
    0,1},{
    1,1},{
    1,0},{
    1,-1}};
int m,n;
void bfs()
{
    
    vis[1][1]=1;
    pre[1][1]={
    -1,-1};
    queue<PI>q;
    q.push({
    1,1});
    while(q.size())
    {
    
        PI k;
        k=q.front();
        q.pop();
        for(int i=0;i<8;i++)
        {
    
            int x=k.first+moves[i][0];
            int y=k.second+moves[i][1];
            if(x>=1&&x<=m&&y>=1&&y<=n&&maze[x][y]==0&&vis[x][y]==0)
            {
    
                vis[x][y]=1;
                q.push({
    x,y});
                pre[x][y]={
    k.first,k.second};
            }
        }
    }
    int x=m,y=n;
    while(x!=-1&&y!=-1)
    {
    
        printf("(%d,%d)\n",x,y);
        PI t=pre[x][y];
        x=t.first;
        y=t.second;
    }


}
int main()
{
    
    scanf("%d%d",&m,&n);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        scanf("%d",&maze[i][j]);
    bfs();
    return 0;
}

这个广搜成功通过。
总结一下深搜和广搜,深搜我看别人比较好的理解方式就是深搜就是“不撞南墙不回头”,意思就是我向前试探一步,然后会一直往前向符合条件的地方试探,也就是比如这题一点位置有八个方向,我先从一个方向开始走,下一次位置又从那个方向开始走,一直走看符不符合退出条件,当走到底时,走不通,撞到南墙时,返回上一个位置,从下一个方向开始走,又走到底,然后走不通时,又返回你走到底的上一个位置。这样可想而知,时间复杂度巨大。因为目前我还是小白,叙述可能有点不清,想更容易理解一下可以搜搜其他的博客,应该讲述的比我好。然后广搜你可以这样理解就是一个石头丢进水中,然后会产生一个波浪,你就可以理解那个波浪的最外层最早碰到终止条件时停止。这样我们搜索最短路径的话就第一次符合终止条件的那一次搜索就是最短路径。讲述可能有点不清楚,由于本人也是刚开始学,也正在学习中,想要讲解更清楚的可以搜搜其他广搜深搜的博客,应该会比我讲的清晰许多。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_46534908/article/details/109239948

智能推荐

Training-Time-Friendly Network for Real-Time Object Detection论文笔记-程序员宅基地

文章浏览阅读301次。(一)Title论文地址:https://arxiv.org/abs/1909.00700代码地址:https://github.com/ZJULearning/ttfnet前言:Light-head,anchor-free,single-stage,TTFNet,作者在文中不断提及encode training samples plays a similar role as increasing the batch size,(二)Summary为了取得训练时间、推理速度以及精度之间的平衡,作_training-time-friendly network for real-time object detection 论文笔记

linux下的mysql 语句命令大全_mysql,linux常用语句-程序员宅基地

文章浏览阅读732次。1.linux下启动mysql的命令:  mysqladmin start  /ect/init.d/mysql start (前面为mysql的安装路径)  2.linux下重启mysql的命令:  mysqladmin restart  /ect/init.d/mysql restart (前面为mysql的安装路径)  3.linux下关闭mysql的命令_mysql,linux常用语句

笔记-变分自编码器(Variational Auto Encoder,VAE)_序列到序列的变分自编码器-程序员宅基地

文章浏览阅读649次。从大数据时代——&gt;人工智能,生活中各场景下的大数据问题都能用大数据+人工智能算法的配方进行求解。诸如分类、回归等有监督学习问题都得到了很好的解决,但监督学习需要大量标注数据,这一限制使得很多场景无法依靠人工智能的红利。因此,无监督学习正慢慢成为研究热点。VAE便是其中的典型代表。VAE的设计结构具有严谨的数学理论指导,粗略看了一遍,没有太理解,在此mark住,以后有需要再回来学习。链接如下:..._序列到序列的变分自编码器

Android studio 混淆打包 proguard-rules.pro 与 bulid.gradle 配置总结_android proguard-rules.pro build.gradle-程序员宅基地

文章浏览阅读229次。现在写的app 基本都是经过混淆了的,如果不混淆, 发布出去,别人一反编译 就可以直接看你的源码了ok 来说一下混淆吧:build.gradle文件apply plugin: 'com.android.application'android { //签名文件 改为自己的路径 signingConfigs { config { keyAlias 'xiao' keyPassword 'key' _android proguard-rules.pro build.gradle

ARM应用系统开发详解:第2章 ARM微处理器的编程模型_thumb mov 改变psr-程序员宅基地

文章浏览阅读1k次。 2.1 ARM微处理器的工作状态从编程的角度看,ARM微处理器的工作状态一般有两种,并可在两种状态之间切换:-第一种为ARM状态,此时处理器执行32位的字对齐的ARM指令;-第二种为Thumb状态,此时处理器执行16位的、半字对齐的Thumb指令。当ARM微处理器执行32位的ARM指令集时,工作在ARM状态;当ARM微处理器执行16位的Thumb指令集时,工作在Thumb状态_thumb mov 改变psr

微信小程序 - 固定头部 列表滚动header吸顶,滚动更新数据_微信小程序自定义头部后怎么吸顶-程序员宅基地

文章浏览阅读3.5k次,点赞4次,收藏7次。demo 地址: https://github.com/iotjin/Jh_weapp效果图:吸顶主要是 position: sticky;.header { background: rgb(230, 230, 230); height: 25px; line-height: 25px; padding-left: 30rpx; font-size: 13px; align-items: center; position: sticky; top: 0;}._微信小程序自定义头部后怎么吸顶

随便推点

AndroidJetpack Livedata最详尽的使用场景分析_globlelivedata-程序员宅基地

文章浏览阅读487次。Livedata 概览LiveData 是一种可观察的数据存储器类。与常规的可观察类不同,LiveData 具有生命周期感知能力如果观察者(由 Observer 类表示)的生命周期处于 STARTED 或 RESUMED 状态,则 LiveData 会认为该观察者处于活跃状态。。LiveData 只会将更新通知给活跃的观察者。为观察 LiveData 对象而注册的非活跃观察者不会收到更改通知。您可以注册与实现 LifecycleOwner 接口的对象配对的观察者。有了这种关系,当相应的 Lifecyc_globlelivedata

练习题-程序员宅基地

文章浏览阅读143次。1:每张纸的厚度为0.08毫米,折纸多少次,高度能超过8848米public class xunhuanyuju { public static void main(String[] args) { int i=0;//i为次数 double h= 0.00008;//h为厚度 while (h < 8848) { i+=1; ..._c语言用二重循环百马百担

贪吃的小q_java 牛客网 贪吃的小q-程序员宅基地

文章浏览阅读195次。牛客题目https://www.nowcoder.com/questionTerminal/d732267e73ce4918b61d9e3d0ddd9182?orderByHotValue=1&page=1&onlyReference=false小Q的父母要出差N天,走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半,但是他又不想在父母回来之前的某一天没有..._java 牛客网 贪吃的小q

常用linux脚本命令_linux下脚本命令-程序员宅基地

文章浏览阅读329次。常用shell脚本命令字符串替换列表List新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants创建一个自定义列表如何创建一个注脚注释也是必不可少的KaTeX数学公式新的甘特图功能,丰富你的文章UML 图表FLowchart流程图导出与导入导出导入字符串替换sed 's/原字符/新字符/g 后面g表示全替换。 sed -i 's/xx/aaa/g' filename 替换_linux下脚本命令

centos 7 搭建web服务器_请简述centos 7下web服务器的安装和状态查询及启动命令-程序员宅基地

文章浏览阅读1w次。centos7安装 这里就是网上下好iso镜像,然后一步步装好,建议初学者选GNONE桌面版方便操作 Apache、Mysql、PHP安装 Apacheapache软件包名称叫做httpdyum install httpd出现提示时一路 y+回车 就好 启动Apache并将其设置为开机启动 systemctl start httpd.service systemctl enab..._请简述centos 7下web服务器的安装和状态查询及启动命令

LightOJ 1282 - Leading and Trailing (求n^k的前三位和后三位)_description given two integers nn n and kk k, find-程序员宅基地

文章浏览阅读1.5k次。1282 - Leading and Trailing PDF (English)StatisticsForumTime Limit: 2 second(s)Memory Limit: 32 MBYou are given two integers: n and k, your_description given two integers nn n and kk k, find the leftmost kk k digits

推荐文章

热门文章

相关标签