用栈解决迷宫问题-Go语言

Posted on | In

原文地址 zhuanlan.zhihu.com

用栈解决迷宫问题-Go语言

问题描述

image-20220416010800925

以上是一个迷宫，我们要从右上角的入口走到左下角的出口。现在要设计一个程序输出可走的路线，如果无法到达出口则输出不能。

问题分析

对于以上的迷宫图我们要用一个二维数组进行模拟：

code

1
2
3
4
5
6
7
8
9
10
const N, M = 8, 8 // 迷宫大小

// 迷宫图
var mg [N + 2][M + 2]int = [N + 2][M + 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},
}

首先要声明一个位置向量结构体：

1
2
3
type pos struct {
	x, y, dir int // dir表示方向:0,1,2,3-右,下,左,上
}

这里如果不存放指向dir的话我们很难知道当前位置点的哪些方向都遍历过了。

然后我们要针对这种位置向量设计一个栈：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// 位置向量栈
type stack []pos

// 入栈
func (this *stack) Push(x pos) { *this = append(*this, x) }

// 出栈
func (this *stack) Pop() pos {
	res := (*this)[len(*this)-1]
	*this = (*this)[0 : len(*this)-1]
	return res
}

// 获取栈顶元素
func (this stack) getTop() pos { return this[len(this)-1] }

// 获取当前栈元素个数
func (this stack) Size() int { return len(this) }

// 判断是否为空栈
func (this stack) Empty() bool { return len(this) == 0 }

// 打印输出
func (this stack) show() {
	for i, v := range this {
		if i != this.Size()-1 {
			fmt.Printf("(%d,%d)->", v.x, v.y)
		} else {
			fmt.Printf("(%d,%d)\n", v.x, v.y)
		}
	}
}

迷宫的路径搜索

graph TD
A(创建路径栈和相关临时变量) --> B[初始位置向量入栈,并标记标记地图] -->C
C{判断是否为空栈} -->|No|I{是否到达终点}
I -->|Yes| K(输出路线)
I -->|No| D[朝四个方向依次进行遍历]
D --> E{是否找到可走路线} -->|Yes| F[记录可走方向,该可走的位置向量入栈]
E -->|No|G[无路可走,所以当前栈顶位置向量出栈并撤回标记]
F --> C
G --> C
C ----->|Yes| H(该迷宫行不通)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
// 迷宫路径搜索
func mgpath(xe, ye int) bool {
	var e pos
	var i, j int
	var find bool
	var st stack
	e.x, e.y, e.dir = 1, 1, -1 // dir=-1表示还没向四个方向搜索过
	st.Push(e)
	mg[e.x][e.y] = -1 // 标记已走过
	for !st.Empty() { // 有路可走
		e = st.getTop()
		if e.x == xe && e.y == ye { // 找到出口
			st.show()
			return true
		}
		find = false
		for e.dir < 4 && !find {
			e.dir++
			switch e.dir {
			case 0: // 右
				i = e.x
				j = e.y + 1
			case 1: // 下
				i = e.x + 1
				j = e.y
			case 2: // 左
				i = e.x
				j = e.y - 1
			case 3: // 上
				i = e.x - 1
				j = e.y
			}
			if mg[i][j] == 0 { // 如果未走过且为空
				find = true
			}
		}
		if find { // 有路可走
			st[st.Size()-1].dir = e.dir // 记录方向，这里如果不记录方向返回的时候还会重新遍历方向导致死循环
			e.x, e.y, e.dir = i, j, -1
			st.Push(e)
			mg[e.x][e.y] = -1
		} else { // 当前位置无路可走
			st.Pop()         // 退回去
			mg[e.x][e.y] = 0 // 撤回
		}
	}
	return false
}

完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
package main

import "fmt"

type pos struct {
	x, y, dir int // dir表示方向:0,1,2,3-右,下,左,上
}

// 位置向量栈
type stack []pos

// 入栈
func (this *stack) Push(x pos) { *this = append(*this, x) }

// 出栈
func (this *stack) Pop() pos {
	res := (*this)[len(*this)-1]
	*this = (*this)[0 : len(*this)-1]
	return res
}

// 获取栈顶元素
func (this stack) getTop() pos { return this[len(this)-1] }

// 获取当前栈元素个数
func (this stack) Size() int { return len(this) }

// 判断是否为空栈
func (this stack) Empty() bool { return len(this) == 0 }

// 打印输出
func (this stack) show() {
	for i, v := range this {
		if i != this.Size()-1 {
			fmt.Printf("(%d,%d)->", v.x, v.y)
		} else {
			fmt.Printf("(%d,%d)\n", v.x, v.y)
		}
	}
}

const N, M = 8, 8 // 迷宫大小

// 迷宫图
var mg [N + 2][M + 2]int = [N + 2][M + 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 mgpath(xe, ye int) bool {
	var e pos
	var i, j int
	var find bool
	var st stack
	e.x, e.y, e.dir = 1, 1, -1 // dir=-1表示还没向四个方向搜索过
	st.Push(e)
	mg[e.x][e.y] = -1 // 标记已走过
	for !st.Empty() { // 有路可走
		e = st.getTop()
		if e.x == xe && e.y == ye { // 找到出口
			st.show()
			return true
		}
		find = false
		for e.dir < 4 && !find {
			e.dir++
			switch e.dir {
			case 0: // 右
				i = e.x
				j = e.y + 1
			case 1: // 下
				i = e.x + 1
				j = e.y
			case 2: // 左
				i = e.x
				j = e.y - 1
			case 3: // 上
				i = e.x - 1
				j = e.y
			}
			if mg[i][j] == 0 { // 如果未走过且为空
				find = true
			}
		}
		if find { // 有路可走
			st[st.Size()-1].dir = e.dir // 记录方向，这里如果不记录方向返回的时候还会重新遍历方向导致死循环
			e.x, e.y, e.dir = i, j, -1
			st.Push(e)
			mg[e.x][e.y] = -1
		} else { // 当前位置无路可走
			st.Pop()         // 退回去
			mg[e.x][e.y] = 0 // 撤回
		}
	}
	return false
}

// 主函数
func main() {
	if mgpath(N, M) {
		fmt.Println("Succuss!") // 迷宫可解
	} else {
		fmt.Println("fail!") // 迷宫无解
	}
}
/*
(1,1)->(1,2)->(2,2)->(3,2)->(3,1)->(4,1)->(5,1)->(5,2)->(5,3)->(6,3)->(6,4)->(6,5)->(7,5)->(8,5)->(8,6)->(8,7)->(8,8)
Succuss!
*/

image-20220416015831474