Go 迷宫算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Go 迷宫算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2814字,纯文字阅读大概需要5分钟。
内容图文
首先读取一个迷宫文件maze.in (第一行是文件的行列 下面是文件内容:1表示墙 0表示此路可走)
如何读取?
// 读取一个二维数组 func readMaze(filename string) [][]int { // 先打开文件 默认是已经存在这个文件 故没有做其他出错处理 file, err := os.Open(filename) if err != nil { panic(err) } //需要先将行、列读出来 利用Fscanf读取var row, col int fmt.Fscanf(file, "%d %d", &row, &col) //创建二维slice 注意:这里是传入参数行row 因为二维数组其实就是:有row这么多一维数组构成 这里是使用切片 maze := make([][]int, row) for i := range maze { maze[i] = make([]int, col) //利用make创建for j := range maze[i] { fmt.Fscanf(file, "%d", &maze[i][j]) } } return maze } func main() { maze := readMaze("mazepractice/maze.in") for _,row := range maze { for _,val := range row { fmt.Printf("%3d",val) } fmt.Println() } }
迷宫算法解读
package main import ( " fmt " " os " ) func readMaze(filename string) [][]int { file, err := os.Open(filename) if err != nil { panic(err) } var row, col int fmt.Fscanf(file, "%d %d", &row, &col) maze := make([][]int, row) for i := range maze { maze[i] = make([]int, col) for j := range maze[i] { fmt.Fscanf(file, "%d", &maze[i][j]) } } return maze } // 定义点的结构体 因为这里是数组 最好不要用x,y定义(以免自己与坐标混淆) type point struct { i, j int } // 定义4个方向分别是:上 左 下 右 方向var dirs = [4]point{ {-1, 0}, {0, -1}, {1, 0}, {0, 1}} // 走迷宫需要从上左下右方向去走,因此坐标会相应的变化 注:这里是利用返回一个新的point 而不是利用指针(当然,指针也可以)func (p point) add(r point) point { return point{p.i + r.i, p.j + r.j} } //判断走的点是不是合理的 有没越界 返回值是点和一个状态值 func (p point) at(grid [][]int) (int, bool) { if p.i < 0 || p.i >= len(grid) { return0, false } if p.j < 0 || p.j >= len(grid[p.i]) { return0, false } return grid[p.i][p.j], true } // 走迷宫的关键算法 通过传入3个参数:二维切片,开始点,结束点 返回的是:一个二维切片 func walk(maze [][]int, start, end point) [][]int { // 这里其实是创建一个走过路线的steps 根据我们读取的文件maze.in规格大小来创建 steps := make([][]int, len(maze)) for i := range steps { steps[i] = make([]int, len(maze[i])) } // 创建一个队列 开始点是(0,0) Q := []point{start} // 队列不空for len(Q) > 0 { cur := Q[0] //cur代表队列开始点(0,0) Q = Q[1:] //去掉队列第一个点 // 发现终点 退出if cur == end { break } // 没有走到的请看for _, dir := range dirs { // 通过上 左 下 右 走这些路 next := cur.add(dir) // 判断走的路线是不是可以走:0 可以走 1 不可以走 当然越界也是不行的 val, ok := next.at(maze) if !ok || val == 1 { continue } // 判断这些点有没有走过:就是不要走回头路 val, ok = next.at(steps) if !ok || val != 0 { continue } // 不是0 可能回到起点 不行的if next == start { continue } // 当前的步骤数 curSteps, _ := cur.at(steps) steps[next.i][next.j] = curSteps + 1// 把这个放在队列的后面 Q = append(Q, next) } } return steps } func main() { maze := readMaze("mazepractice/maze.in") steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1}) // 打印实际走的这个数组for _, row := range steps { for _, val := range row { fmt.Printf("%3d", val) } fmt.Println() } lessStep := steps[len(maze)-1][len(maze[0])-1] fmt.Printf("这个迷宫最少需要%d步走完",lessStep) // TODO: construct path from steps }
左边是读取的文件,右边是输出结果:
左边是读取的文件,右边是输出结果:
原文:https://www.cnblogs.com/ycx95/p/9397920.html
内容总结
以上是互联网集市为您收集整理的Go 迷宫算法全部内容,希望文章能够帮你解决Go 迷宫算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。