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

火蜥蜴 · · 1564 次点击 · · 开始浏览

这是一个创建于的文章，其中的信息可能已经有所发展或是发生改变。

问题

给定一个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("\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)
}