算法：迷宫问题-递归实现
算法 大约 4247 字初始化迷宫
初始化一个8行7的二维数组。
maze := make([][7]int, 8)
//Print(maze)
for i := 0; i < 8; i++ {
maze[i][0] = 1
maze[i][6] = 1
if i < 7 {
maze[0][i] = 1
maze[7][i] = 1
}
}
maze[3][1] = 1
maze[3][2] = 1得到迷宫如下
1 1 1 1 1 1 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1 递归寻找路径
人为定义算法：下 右 上 左 按此顺序走，若没走过则先置为2，再递归走下一步，若走过了或走不通则置为3。
func SetWay(maze [][7]int, i, j int) bool {
if maze[6][5] == 2 {
return true
} else {
if maze[i][j] == 0 {
maze[i][j] = 2
Print(maze)
// 下 右 上 左
if SetWay(maze, i+1, j) { // 往下
return true
} else if SetWay(maze, i, j+1) { // 往右
return true
} else if SetWay(maze, i-1, j) { // 往上
return true
} else if SetWay(maze, i, j-1) { // 往左
return true
} else {
maze[i][j] = 3
Print(maze)
return false
}
} else {
// 数值为1, 2, 3的情况都返回false
return false
}
}
}测试代码
// 初始化迷宫代码省略
SetWay(maze, 1, 1)输出
1 1 1 1 1 1 1
1 2 0 0 0 0 1
1 2 2 0 0 0 1
1 1 1 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 0 0 1
1 0 0 2 2 2 1
1 1 1 1 1 1 1设置挡板
设置挡板帮助理解递归
func main() {
maze := make([][7]int, 8)
//Print(maze)
for i := 0; i < 8; i++ {
maze[i][0] = 1
maze[i][6] = 1
}
for j := 0; j < 7; j++ {
maze[0][j] = 1
maze[7][j] = 1
}
maze[3][1] = 1
maze[3][2] = 1
maze[3][3] = 1
maze[2][3] = 1
maze[1][3] = 1
Print(maze)
SetWay(maze, 1, 1)
}输出
1 1 1 1 1 1 1
1 0 0 1 0 0 1
1 0 0 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 0 1 0 0 1
1 0 0 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 0 1 0 0 1
1 2 0 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 0 1 0 0 1
1 2 2 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 2 1 0 0 1
1 2 2 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 3 1 0 0 1
1 2 2 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 3 1 0 0 1
1 2 3 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 2 3 1 0 0 1
1 3 3 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
1 1 1 1 1 1 1
1 3 3 1 0 0 1
1 3 3 1 0 0 1
1 1 1 1 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1
-------------------------
阅读 139 · 发布于 2021-01-29
———— END ————
扫描下方二维码关注公众号和小程序↓↓↓
昵称：