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

## 问题

``````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)
}
``````

## 最后

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

## 问题

``````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)
}
``````