前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【转载】用队列求解迷宫最短路径及其应用(围住神经猫)

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

作者头像
李海彬
发布2018-03-27 14:42:41
1.7K0
发布2018-03-27 14:42:41
举报
文章被收录于专栏:Golang语言社区
问题

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

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

代码语言:javascript
复制
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("\n")

    for k != 0 {

        j = k

        k = queue.data[k].pre

        queue.data[j].pre = -1

    }

    k = 0

    fmt.Println("迷宫路径如下:\n")

    for k < maxSize {

        if queue.data[k].pre == -1 {

            ns++

            fmt.Printf("\t(%d, %d)", queue.data[k].i, queue.data[k].j)

            if ns%5 == 0 {

                fmt.Println("\n")

            }

        }

        k++

    }

}



func main() {

    gameSearch(1, 1, 8, 8)

}

运行结果

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-07-30,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 Golang语言社区 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档