用隊(duì)列求解迷宮最短路徑及其應(yīng)用(圍住神經(jīng)貓)

Achilles 發(fā)布于2019-06-27 17:07 / 3556人閱讀

摘要：對(duì)應(yīng)迷宮數(shù)組為實(shí)現(xiàn)語(yǔ)言實(shí)現(xiàn)求解方塊類(lèi)型方塊行號(hào)方塊列號(hào)上一個(gè)方塊在隊(duì)列中位置順序隊(duì)進(jìn)隊(duì)順時(shí)針迷宮路徑如下運(yùn)行結(jié)果應(yīng)用圍住神經(jīng)貓游戲使用寫(xiě)的項(xiàng)目源碼下載體驗(yàn)最后附上我喜歡的歌的英文翻譯心做

問(wèn)題

給定一個(gè)M×N的迷宮圖,求一條從指定入口到出口的最短路徑.假設(shè)迷宮圖如圖所示(M=8, N=8)

對(duì)于圖中的每個(gè)方塊,空白表示通道,陰影表示墻。所求路徑必須是簡(jiǎn)單路徑，即在求得路徑上不能重復(fù)出現(xiàn)同一通道塊。
為了算法方便，在迷宮外圍加了一道圍墻。
對(duì)應(yīng)迷宮數(shù)組為：

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},
    }

實(shí)現(xiàn)

go語(yǔ)言實(shí)現(xiàn)求解:

package main

import (
    "fmt"
)

const (
    M = 8
    N = 8
)

// 方塊類(lèi)型
type Box struct {
    i   int // 方塊行號(hào)
    j   int // 方塊列號(hào)
    pre int // 上一個(gè)方塊在隊(duì)列中位置
}

// 順序隊(duì)
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)進(jìn)隊(duì)
    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
        }
        // 順時(shí)針
        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)
}

運(yùn)行結(jié)果

應(yīng)用

圍住神經(jīng)貓

游戲使用C#寫(xiě)的,項(xiàng)目源碼
下載體驗(yàn)

最后

附上我喜歡的歌的英文翻譯
心做し