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

问题

×ばつ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)
}

运行结果

应用

围住神经猫

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

最后

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

本文来自:Segmentfault

感谢作者:火蜥蜴

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

• 编辑
• 预览