golang笔记12--迷宫的广度优先搜索

• ​​1 介绍​​
• ​​2 迷宫的广度优先搜索​​

• ​​2.1 迷宫算法解析​​
• ​​2.2 迷宫代码实现​​

• ​​3 说明​​
• ​​4 介绍​​

1 介绍

本文继上文 ​​golang笔记11–go语言并发编程模块 channel​​​， 进一步了解 go 语言经典案例 --迷宫的广度优先搜索，以及相应注意事项。

具体包括 :迷宫算法解析、迷宫代码实现 等内容。

2 迷宫的广度优先搜索

2.1 迷宫算法解析

本案例中使用的迷宫结构如下：

思路：

先找出所有1步的点(标记走的步数为1)，

然后在上一步的基础上找到2步的所有点(标记走的步数为2)，

然后再在上一步基础上找到3步所有的点(标记走的步数为3)，

…

一直如此循环，直到找到终点(出口) 或者 无法继续下一步的时候终止程序。按照上述思路遍历，最终结果如下图，第13步的时候到达了终点；此时从终点13按照逆序的方向(由于顺序的话会出现选择多个值的情况，因此逆序找最优解)，依次找到唯一的 13->12->11->…->2->1->0 最短路径即为迷宫的最优解。

2.2 迷宫代码实现

vim maze.in
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

vim mazi.go
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
}

func printArray(arr [][]int) {
  fmt.Println("original maze:")
  for _, row := range arr {
    for _, col := range row {
      fmt.Printf("%3d", col)
    }
    fmt.Println()
  }
}

type point struct {
  i, j int
}

// 定义左上右下 4 个方向
var dirs = [4]point{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}

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) {
    return 0, false
  }
  if p.j < 0 || p.j >= len(grid[p.i]) {
    return 0, false
  }
  return grid[p.i][p.j], true
}

func walk(maze [][]int, start, end point) [][]int {
  fmt.Println("start: ", start, "\tend: ", end)
  steps := make([][]int, len(maze))
  for i := range steps {
    steps[i] = make([]int, len(maze[i]))
  }

  Q := []point{start}
  for len(Q) > 0 {
    cur := Q[0]
    Q = Q[1:]
    // 终点则返回
    if cur == end {
      break
    }
    for _, dir := range dirs {
      next := cur.add(dir)
      // 1）maze 下一个节点为0则可以走； 2）下一个节点的steps为0(不为0则表示为到过该点)； 3）下一个节点不能是起点；
      val, ok := next.at(maze)
      if !ok || val == 1 {
        continue
      }
      val, ok = next.at(steps)
      if !ok || val != 0 {
        continue
      }
      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("chapter12/maze.in")
  printArray(maze)
  steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
  fmt.Println("steps maze:")
  for _, row := range steps {
    for _, val := range row {
      fmt.Printf("%3d", val)
    }
    fmt.Println()
  }
}
输出：
original maze:
  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
start:  {0 0}   end:  {5 4}
steps maze:
  0  0  4  5  6
  1  2  3  0  7
  2  0  4  0  8
  0  0  0 10  9
  0  0 12 11  0
  0  0 13 12 13      

3 说明

4 介绍

1. 软件环境

   go版本：go1.15.8

   操作系统：Ubuntu 20.04 Desktop

   Idea：2020.01.04

2. 参考文档

   ​​​广度优先遍历 --百度百科​​