Tim

一枚野生程序员~

  • 主页
  • 分类
  • 标签
  • 归档
  • 关于
所有文章 工具

Tim

一枚野生程序员~

  • 主页
  • 分类
  • 标签
  • 归档
  • 关于

回溯思想解决迷宫问题

阅读数:次 2018-04-25
字数统计: 1.4k字   |   阅读时长≈ 6分

mark
这是几个由二维数组构成的迷宫,简单的迷宫,多通路不带环的迷宫,多通路带环的迷宫!对于简单迷宫我们需要判断是否有出口!对于多通路不带环的迷宫我们需要确定出口并且判断最短路径,对于通路间带环的迷宫我们需要找出最短路径!

算法思想:回溯

回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为“回溯点”。
在本题中也用到的就是回溯, 就是把走过的点坐标压栈,遇到无路可走的情况就开始回溯,也就是出栈!
总体思路就是:

  • 现将入口点压栈,走过的地方标记为2
  • 每走一步就将坐标压栈,判断下一步可以走的地方,如果能走就压栈
  • 当上下左右四个方向都不能走的时候就回溯
  • 直到回溯到入口点还是没有其他方向可以走,那么循环结束,也就意味着没有出口!
  • 使用一个方法判断坐标点是否合法的,注意数组越界的情况,首先不越界,其次坐标点值为1的时候才是合法的
  • 对于多通路迷宫首先需要明白当右边出现两个入口点的时候只需要判断列 == N即可认为是找到了出口
  • 首先下一个点可以走的条件是:该点值为1或者该点值比上一个+1还大
  • 每走一步值就+1,入口点值设置为2

    代码实现

    所有代码位于GitHub:https://github.com/zouchanglin/VSworkspace/tree/master/67_Maze,对于简单迷宫的核心代码:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    int CheckAccess(Pos next)
    {
    //判断越界的情况
    if(next._col >= 0 &&next._row>=0
    && next._col<N && next._row<N)
    {
    //1才是表示通路
    if (maze[next._row][next._col] == 1)
    {
    return 1;
    }
    }
    //return 0表示不可以通过
    return 0;
    }
    int MazeGetPath(Pos entry,Pos exit)
    {
    Pos cur = entry;//cur记录起始位置

    Stack path;
    StackInit(&path);
    StackPush(&path, entry);//将起始坐标压栈
    while (StackEmpty(&path))
    {
    cur = StackTop(&path);
    if ((cur._row == exit._row) && (cur._col == exit._col))
    return 1;
    //探测下一次可以去的地方
    maze[cur._row][cur._col] = 2;//标记上一次走过的位置
    //上
    Pos next = cur;
    next._row -= 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }
    //下
    next = cur;
    next._row += 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }
    //左
    next = cur;
    next._col -= 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }
    //右
    next = cur;
    next._col += 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }

    //回溯
    StackPop(&path);
    }
    return 0;
    }
    对于稍复杂的迷宫的核心代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    int CheckAccess(Pos next)
    {
    //判断越界的情况
    if(next._col >= 0 &&next._row>=0
    && next._col<N && next._row<N)
    {
    //1才是表示通路
    if (maze[next._row][next._col] == 1)
    {
    return 1;
    }
    }
    //return 0表示不可以通过
    return 0;
    }

    int MazeCheckIsAccess(Pos cur, Pos next)
    {
    //判断越界的情况
    if ((next._col >= 0 && next._row >= 0 && next._col<N && next._row<N)
    &&(maze[next._row][next._col] == 1 || maze[next._row][next._col]>maze[cur._row][cur._col]+1))
    {
    return 1;
    }
    //return 0表示不可以通过
    return 0;
    }

    int pathsize = 0;

    int MazeGetPath(Pos entry,Pos exit)
    {
    Pos cur = entry;//cur记录起始位置

    Stack path;
    StackInit(&path);
    StackPush(&path, entry);//将起始坐标压栈

    maze[entry._row][entry._col] = 2;
    while (StackEmpty(&path))
    {
    cur = StackTop(&path);
    maze[cur._row][cur._col] = 2;//标记上一次走过的位置
    //if ((cur._row == exit._row) && (cur._col == exit._col))
    if (cur._col == 5)
    {
    //如果只找一条通路则返回
    //return 1;
    //StackDestory(&path);
    if (pathsize == 0||
    StackSize(&path) < pathsize)
    {
    pathsize = StackSize(&path);
    }
    }
    //探测下一次可以去的地方
    //上
    Pos next = cur;
    next._row -= 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }
    //下
    next = cur;
    next._row += 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }
    //左
    next = cur;
    next._col -= 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }
    //右
    next = cur;
    next._col += 1;
    if (CheckAccess(next))
    {
    StackPush(&path, next);
    continue;
    }

    //回溯
    StackPop(&path);
    }
    return 0;
    }


    int MazeGetShortPath(Pos entry, Pos exit)
    {
    Pos cur = entry;//cur记录起始位置

    Stack path;
    StackInit(&path);
    StackPush(&path, entry);//将起始坐标压栈


    maze[entry._row][entry._col] = 2;
    while (StackEmpty(&path))
    {
    cur = StackTop(&path);
    if (cur._col == 5)
    {
    //如果只找一条通路则返回
    //return 1;
    //StackDestory(&path);
    if (pathsize == 0 ||
    StackSize(&path) < pathsize)
    {
    pathsize = StackSize(&path);
    }
    }
    //探测下一次可以去的地方
    //上
    Pos next = cur;
    next._row -= 1;
    if (MazeCheckIsAccess(cur, next))
    {
    maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
    StackPush(&path, next);
    continue;
    }
    //下
    next = cur;
    next._row += 1;
    if (MazeCheckIsAccess(cur, next))
    {
    maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
    StackPush(&path, next);
    continue;
    }
    //左
    next = cur;
    next._col -= 1;
    if (MazeCheckIsAccess(cur, next))
    {
    maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
    StackPush(&path, next);
    continue;
    }
    //右
    next = cur;
    next._col += 1;
    if (MazeCheckIsAccess(cur, next))
    {
    maze[next._row][next._col] = maze[cur._row][cur._col] + 1;
    StackPush(&path, next);
    continue;
    }

    //回溯
    StackPop(&path);
    }
    return 0;
    }
    mark
    mark
赏

谢谢你请我喝咖啡

支付宝
微信
  • 本文作者: Tim
  • 本文链接: https://zouchanglin.cn/2219561060.html
  • 版权声明: 本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 许可协议。转载请注明出处!
  • 栈
  • 回溯
  • 数据结构与算法

扫一扫,分享到微信

《C陷阱与缺陷》笔记
Android学习日志
  1. 1. 算法思想:回溯
  2. 2. 代码实现
© 2017-2021 Tim
本站总访问量次 | 本站访客数人
  • 所有文章
  • 工具

tag:

  • 生活
  • Android
  • 索引
  • MySQL
  • 组件通信
  • Nginx
  • JavaSE
  • JUC
  • JavaWeb
  • 模板引擎
  • 前端
  • Linux
  • 计算机网络
  • Docker
  • C/C++
  • JVM
  • 上传下载
  • JavaEE
  • SpringCloud
  • Golang
  • Gradle
  • 网络安全
  • 非对称加密
  • IDEA
  • SpringBoot
  • Jenkins
  • 字符串
  • vim
  • 存储
  • 文件下载
  • Mac
  • Windows
  • NIO
  • RPC
  • 集群
  • 微服务
  • SSH
  • 配置中心
  • XML
  • Chrome
  • 压力测试
  • Git
  • 博客
  • 概率论
  • 排序算法
  • 分布式
  • 异常处理
  • 文件系统
  • 哈希
  • openCV
  • 栈
  • 回溯
  • SpringCore
  • 流媒体
  • rtmp
  • 面向对象
  • Vue
  • ElementUI
  • 软件工程
  • 异步
  • 自定义UI
  • ORM框架
  • 模块化
  • 交互式
  • Jsoup
  • Http Client
  • LRUCache
  • RabbitMQ
  • 消息通信
  • 服务解耦
  • 负载均衡
  • 权限
  • 多线程
  • 单例模式
  • Protobuf
  • 序列化
  • Python
  • m3u8
  • 堆
  • 二叉树
  • 自定义View
  • 观察者模式
  • 设计模式
  • 线程池
  • 动态扩容
  • 高可用
  • GC
  • ffmpeg
  • SpringMVC
  • REST
  • Redis
  • 缓存中间件
  • UML
  • Maven
  • Netty
  • 高性能网络
  • IPC通信
  • IO
  • Stream
  • 发布订阅
  • SQLite
  • Hash
  • 集合框架
  • 链表
  • Lambda
  • 汇编语言
  • 组件化
  • Router
  • 开发工具

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录(注意不是yilia-plus根目录)执行以下命令:
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置:

      jsonContent:
        meta: false
        pages: false
        posts:
          title: true
          date: true
          path: true
          text: false
          raw: false
          content: false
          slug: false
          updated: false
          comments: false
          link: false
          permalink: false
          excerpt: false
          categories: false
          tags: true
    

  • 思维导图
  • PDF工具
  • 无损放大
  • 代码转图
  • HTTPS证书