广度优先算法走迷宫

2020-02-20 08:03:38 130 0 Golang

实现结果

结果.png

迷宫地图文件

第一行为 行列标识 此迷宫为6行5列
1为墙 0为路

6 5
0 1 0 0 0
0 0 0 1 0
0 1 0 1 0
1 1 1 0 0
0 1 0 0 1
0 1 0 0 0

思路

从起点开始,朝四个方向探索,每个方向只探索一格,如果那一格合法(未走过且未越界)则记录从起点到达这个点所需步数并加入探索队列,探索完四个方向后从探索队列中取一个出来继续探索,以此类推,直到找到终点。探索完毕后将会得到一个新的地图,地图中记录了所有可到达区域,并标识了到达指定点所需步数。

func work(maze [][]int, start, end point) [][]int { // 记录一下可以走的地方 steps := make([][]int, len(maze)) for i := range steps{ steps[i] = make([]int, len(maze[i])) } // 从起点开始走 queue := []point{start} // 开始探索 for len(queue) > 0 { // 取出当前走的坐标 current := queue[0] queue = queue[1:] if current == end { break } // 探索各个方向 for _, dir := range dirs{ next := current.add(dir) val, ok := next.at(maze) // 越界或碰到墙则跳过 if !ok || val == 1 { continue } val, ok = next.at(steps) // 走过了或者回到起点了跳过 if !ok || val != 0 || next == start { continue } currentStep, _ := current.at(steps) // 记录一下多少步能到这 steps[next.i][next.j] = currentStep + 1 // 加入探索队列 queue = append(queue, next) } } return steps }

根据新的地图从终点开始逆向探索,得出无重复路程的路线

// 从终点开始逆向查找 curr := end currStep, _ := curr.at(steps) route := []point{curr} for curr != start { for _, dir := range dirs{ next := curr.add(dir) step, ok := next.at(steps) // 越界或不是当前这一步的上一步 跳过 if !ok || step != currStep - 1 { continue } // 可以继续往下走 currStep = step route = append(route, next) curr = next break } } // 打印路线坐标 for i := len(route) - 1; i >= 0 ; i-- { fmt.Printf("%v ", route[i]) }

完整代码

package main import ( "os" "fmt" ) type point struct { i, j int } // 移动一步 func (p point) add(dir point) point { return point{p.i + dir.i, p.j + dir.j} } // 当前点校验 func (p point) at(grid [][]int) (int, bool) { // 越界 if p.i < 0 || p.j < 0 || p.i >= len(grid) || p.j >= len(grid[p.i]) { return 0, false } // 返回从起点到这个点需要走多少步, 未记录的则返回0 return grid[p.i][p.j], true } // 实现 Stringer 接口 格式化输出 func (p point) String() string { return fmt.Sprintf("(%d,%d)", p.i, p.j) } var dirs = [4]point{ {-1, 0}, // 上移 {0, -1}, // 左移 {1, 0}, // 下移 {0, 1}, // 右移 } // read maze func readMaze(filename string) (maze [][]int) { var row, col int file, err := os.Open(filename) if err != nil { panic(err) } _, err = fmt.Fscanf(file, "%d %d", &row, &col) if err != nil { panic(err) } maze = make([][]int, row) for i := range maze{ maze[i] = make([]int, col) fmt.Fscanf(file, "%d") for j := range maze[i] { fmt.Fscanf(file, "%d", &maze[i][j]) } } return maze } func work(maze [][]int, start, end point) [][]int { // 记录一下可以走的地方 steps := make([][]int, len(maze)) for i := range steps{ steps[i] = make([]int, len(maze[i])) } // 从起点开始走 queue := []point{start} // 开始探索 for len(queue) > 0 { // 取出当前走的坐标 current := queue[0] queue = queue[1:] if current == end { break } // 探索各个方向 for _, dir := range dirs{ next := current.add(dir) val, ok := next.at(maze) // 越界或碰到墙则跳过 if !ok || val == 1 { continue } val, ok = next.at(steps) // 走过了或者回到起点了跳过 if !ok || val != 0 || next == start { continue } currentStep, _ := current.at(steps) // 记录一下多少步能到这 steps[next.i][next.j] = currentStep + 1 // 加入探索队列 queue = append(queue, next) } } return steps } func main() { // 读取迷宫地图 maze := readMaze("maze.map") start, end := point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1} // 打印一下 for _, row := range maze { for _, val := range row { fmt.Printf("%d ", val) } fmt.Println() } fmt.Println("----------------------------------------") // 开始计算,传入地图、起点、终点 // steps 标识了迷宫中所有可以去的坐标,以及去对应坐标所需步数 steps := work(maze, start, end) for _, row := range steps { for _, val := range row { fmt.Printf("%3d ", val) } fmt.Println() } fmt.Println("----------------------------------------") // 从终点开始逆向查找 curr := end currStep, _ := curr.at(steps) route := []point{curr} for curr != start { for _, dir := range dirs{ next := curr.add(dir) step, ok := next.at(steps) // 越界或不是当前这一步的上一步 跳过 if !ok || step != currStep - 1 { continue } // 可以继续往下走 currStep = step route = append(route, next) curr = next break } } // 打印路线坐标 for i := len(route) - 1; i >= 0 ; i-- { fmt.Printf("%v ", route[i]) } }

评论

:doodle { @grid: 32 / 100vmax; } @random { border-top: 1px solid #60569e; } @random { border-left: 1px solid #60569e; } @random(.2) { :after { content: ''; background: hsl(@rand(360), 60%, 70%); @size: @rand(3px); } }