用栈深度优先算法解决迷宫问题-Go语言

用栈深度优先算法解决迷宫问题-Go语言 问题描述

以上是一个迷宫，我们要从右上角的入口走到左下角的出口。

现在要设计一个程序输出可走的路线，如果无法到达出口则输出不能。

问题分析

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

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

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

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

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

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

// 位置向量栈
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)
		}
	}
}

迷宫的路径搜索

// 迷宫路径搜索
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
}

完整代码

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!
*/