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

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)

}