用队列求解迷宫最短路径及其应用(围住神经猫)

Achilles 发布于2019-06-27 17:07 / 3449人阅读

摘要：对应迷宫数组为实现语言实现求解方块类型方块行号方块列号上一个方块在队列中位置顺序队进队顺时针迷宫路径如下运行结果应用围住神经猫游戏使用写的项目源码下载体验最后附上我喜欢的歌的英文翻译心做

问题

给定一个M×N的迷宫图,求一条从指定入口到出口的最短路径.假设迷宫图如图所示(M=8, N=8)

对于图中的每个方块,空白表示通道,阴影表示墙。所求路径必须是简单路径，即在求得路径上不能重复出现同一通道块。
为了算法方便，在迷宫外围加了一道围墙。
对应迷宫数组为：

var gameMap = [M + 2][N + 2]int{
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
        {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    }

实现

go语言实现求解:

package main

import (
    "fmt"
)

const (
    M = 8
    N = 8
)

// 方块类型
type Box struct {
    i   int // 方块行号
    j   int // 方块列号
    pre int // 上一个方块在队列中位置
}

// 顺序队
type Queue struct {
    data  []Box
    front int
    rear  int
}

var (
    gameMap = [M + 2][N + 2]int{
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 1, 0, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 1, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0, 0, 1},
        {1, 0, 1, 1, 1, 0, 1, 1, 0, 1},
        {1, 1, 0, 0, 0, 0, 0, 0, 0, 1},
        {1, 1, 1, 1, 1, 1, 1, 1, 1, 1},
    }
)

func gameSearch(xStart, yStart, xEnd, yEnd int) bool {
    var i, j, di int
    find := false
    var queue Queue
    queue.data = []Box{}
    queue.front = -1
    queue.rear = -1
    queue.rear++
    queue.data = append(queue.data, Box{})
    queue.data[queue.rear].i = xStart
    queue.data[queue.rear].j = yStart // (xStart, yStart)进队
    queue.data[queue.rear].pre = -1
    gameMap[xStart][yStart] = -1
    for queue.front != queue.rear && !find {
        queue.front++
        i = queue.data[queue.front].i
        j = queue.data[queue.front].j
        if i == xEnd && j == yEnd {
            find = true
            printPath(&queue, queue.front)
            return true
        }
        // 顺时针
        for di = 0; di < 4; di++ {
            switch di {
            case 0:
                i = queue.data[queue.front].i - 1
                j = queue.data[queue.front].j
            case 1:
                i = queue.data[queue.front].i
                j = queue.data[queue.front].j + 1
            case 2:
                i = queue.data[queue.front].i + 1
                j = queue.data[queue.front].j
            case 3:
                i = queue.data[queue.front].i
                j = queue.data[queue.front].j - 1
            }
            if gameMap[i][j] == 0 {
                queue.rear++
                queue.data = append(queue.data, Box{})
                queue.data[queue.rear].i = i
                queue.data[queue.rear].j = j
                queue.data[queue.rear].pre = queue.front
                gameMap[i][j] = -1
            }
        }
    }
    return false
}

func printPath(queue *Queue, front int) {
    var k, j, ns = front, 0, 0
    var maxSize = len(queue.data)
    fmt.Println("
")
    for k != 0 {
        j = k
        k = queue.data[k].pre
        queue.data[j].pre = -1
    }
    k = 0
    fmt.Println("迷宫路径如下：
")
    for k < maxSize {
        if queue.data[k].pre == -1 {
            ns++
            fmt.Printf("	(%d, %d)", queue.data[k].i, queue.data[k].j)
            if ns%5 == 0 {
                fmt.Println("
")
            }
        }
        k++
    }
}

func main() {
    gameSearch(1, 1, 8, 8)
}

运行结果

应用

围住神经猫

游戏使用C#写的,项目源码
下载体验

最后

附上我喜欢的歌的英文翻译
心做し

idc机房托管私有云迷宫最短路径 c语言最短路径算法应用在哪些方面最短路径最短路径问题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/23303.html

2017-07-22 前端日报

摘要：前端日报精选任何网站都可以变成但我们需要做得更好译高性能个新工具加速你的应用在生产环境中使用记录日志手把手教你用开发一个发布中文译继承实例译基于背后的合理化，而非设计掘金实现哪家强中的众成翻译快速入门个人文章一个基于区块链的深网 2017-07-22 前端日报精选任何网站都可以变成 PWA —— 但我们需要做得更好[译] 高性能 React：3 个新工具加速你的应用在生产环境中使用...

endless_road 2019-08-20 18:14 评论0 收藏0
用并查集(find-union)实现迷宫算法以及最短路径求解

摘要：本人邮箱欢迎转载转载请注明网址代码已经全部托管有需要的同学自行下载引言迷宫对于大家都不会陌生那么迷宫是怎么生成已经迷宫要如何找到正确的路径呢用代码又怎么实现带着这些问题我们继续往下看并查集朋友圈有一种算法就做并查集什么意思呢比如现在有零本人邮箱: 欢迎转载,转载请注明网址 http://blog.csdn.net/tianshi_kcogithub: https://github.c...

xiangchaobin 2019-08-16 10:30 评论0 收藏0
算法第四版4.1-无向图详解

摘要：树是一副无环连通图。互不相连的树组成的集合称为森林。表示无向图的数据类型图的基本操作的两个构造，得到顶点数和边数，增加一条边。该方法不符合第一个条件，上百万个顶点的图是很常见的空间不满足。四种重要的图模型：无向图（简单连接）有向图（连接有方向性）加权图（连接带有权值）加权有向图（连接既有方向性又带有权值）无向图定义：由一组顶点和一组能够将两个顶点相连的边组成。特殊：...

scola666 2019-08-14 17:53 评论0 收藏0
基于JavaScript求解八数码最短路径并生成动画效果

摘要：写在最前本次分享一下通过广度优先搜索解决八数码问题并展示其最短路径的动画效果。一个排列中逆序的总数就称为这个排列的逆序数。如果起始状态与结束状态的逆序数的奇偶性相同，则说明状态可达，反之亦然。写在最前本次分享一下通过广度优先搜索解决八数码问题并展示其最短路径的动画效果。欢迎关注我的博客，不定期更新中—— 效果预览该效果为从[[2, 6, 3],[4, 8, 0],[7, 1, ...

Jioby 2019-08-26 11:30 评论0 收藏0
王者编程大赛之五 — 最短路径

摘要：由于是从顶点到的最短路径，则有。算法流程根据最短路径的最优子结构性质，提出了以最短路径长度递增，逐次生成最短路径的算法。相关文章王者编程大赛之一王者编程大赛之二蓄水池王者编程大赛之三背包王者编程大赛之四约瑟夫环首发于樊浩柏科学院自如年底就会拥有 50W 间房子，大家知道每间房房子都是需要配置完才能出租给自如客的，整个房租的配置过程是很复杂的，每天都需要大量的物流师傅将家电、家具...

yuanzhanghu 2019-07-01 12:36 评论0 收藏0