go 广度搜索案例（迷宫）

  1 package main
  2 
  3 import (
  4     "fmt"
  5     "os"
  6 )
  7 
  8 /*
  9 *将文档结构读入到切片中（二维数组）
 10 *row, col   行数  列数  （文档第一行数据）
 11 *fmt.Fscanf  逐一字符读取 （遇到换行返回值为0）***Fscan（遇到换行视为空白）***
 12 *
 13  */
 14 func readMaze(filename string) [][]int {
 15     file, err := os.Open(filename)
 16     if err != nil {
 17         panic(err)
 18     }
 19 
 20     var row, col int
 21     fmt.Fscanf(file, "%d %d", &row, &col)
 22 
 23     maze := make([][]int, row)
 24     for i := range maze {
 25         maze[i] = make([]int, col)
 26         for j := range maze[i] {
 27             fmt.Fscanf(file, "%d", &maze[i][j])
 28         }
 29     }
 30 
 31     return maze
 32 }
 33 
 34 //定义点位
 35 type point struct {
 36     i, j int
 37 }
 38 
 39 //运算的坐标点左、下、右、上
 40 var dirs = [4]point{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
 41 
 42 //运算
 43 func (p point) add(r point) point {
 44     return point{p.i + r.i, p.j + r.j}
 45 }
 46 
 47 //检查坐标点是否超出范围
 48 func (p point) at(grid [][]int) (int, bool) {
 49     if p.i < 0 || p.i >= len(grid) {
 50         return 0, false
 51     }
 52 
 53     if p.j < 0 || p.j >= len(grid[p.i]) {
 54         return 0, false
 55     }
 56 
 57     return grid[p.i][p.j], true
 58 }
 59 
 60 /**
 61  *行走实现路线
 62  *1、新建切片数组  记录总行和列数   填充步数
 63  *
 64  *
 65  *
 66 **/
 67 func walk(maze [][]int, start, end point) [][]int {
 68     steps := make([][]int, len(maze)) // slice
 69     for i := range steps {
 70         steps[i] = make([]int, len(maze[i]))
 71     }
 72 
 73     Q := []point{start}
 74 
 75     for len(Q) > 0 {
 76         cur := Q[0] //队列  多数组 依次
 77         Q = Q[1:]
 78 
 79         if cur == end {
 80             break
 81         }
 82         //排除走过的不能走的
 83         for _, dir := range dirs {
 84             next := cur.add(dir)
 85 
 86             val, ok := next.at(maze)
 87             if !ok || val == 1 {
 88                 continue
 89             }
 90 
 91             val, ok = next.at(steps)
 92             if !ok || val != 0 {
 93                 continue
 94             }
 95 
 96             if next == start {
 97                 continue
 98             }
 99 
100             curSteps, _ := cur.at(steps)
101             steps[next.i][next.j] = curSteps + 1
102 
103             Q = append(Q, next)
104         }
105     }
106 
107     return steps
108 }
109 
110 func main() {
111 
112     maze := readMaze("maze.in")
113 
114     steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
115 
116     for _, row := range steps {
117         for _, val := range row {
118             fmt.Printf("%3d", val)
119         }
120         fmt.Println()
121     }
122 
123     // TODO: construct path from steps
124 }
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