算法:迷宫问题-递归实现
算法 About 4,247 words初始化迷宫
初始化一个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
-------------------------
Views: 2,203 · Posted: 2021-01-29
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb/LiteNote扫描下方二维码关注公众号和小程序↓↓↓
Loading...