算法:迷宫问题-递归实现
算法 大约 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
-------------------------
阅读 742 · 发布于 2021-01-29
————        END        ————
Give me a Star, Thanks:)
https://github.com/fendoudebb扫描下方二维码关注公众号和小程序↓↓↓

昵称:
随便看看
换一批
-
软考-系统架构设计师:数据库设计过程阅读 1304
-
MySQL 全文检索 FULLTEXT 搜索不到内容阅读 1843
-
GoJS 给右键菜单中的按钮添加分割线阅读 536
-
PostgreSQL 获取本月第一天时间戳等信息阅读 3061
-
JVM:运行时数据区之程序计数器阅读 112
-
Gradle 生成 gradlew 设置版本及属性阅读 3725
-
Android RadioButton 的点击效果阅读 2435
-
Nginx(OpenResty) 去掉默认错误页面中的版本号阅读 631
-
MongoDB 批量导入 csv 数据阅读 3203
-
MySQL 中文全文检索 ngram 处理停止词阅读 3257