1. package main
    3. import (
    4.     "fmt"
    5.     "os"
    6. )
    8. func readMaze(fileName string) [][]int {
    9.     file, err := os.Open(fileName)
    10.     if err != nil {
    11.         panic(err)
    12.     }
    14.     var row, col int
    15.     fmt.Fscanf(file, "%d %d", &row, &col)
    17.     maze := make([][]int, row)
    18.     for i := range maze {
    19.         maze[i] = make([]int, col)
    20.         for j := range maze[i] {
    21.             fmt.Fscanf(file, "%d", &maze[i][j])
    22.         }
    23.     }
    24.     return maze
    25. }
    27. type point struct {
    28.     i, j int
    29. }
    31. var dirs = [4]point{
    32.     {-1, 0},
    33.     {0, -1},
    34.     {1, 0},
    35.     {0, 1},
    36. }
    38. func (p point) add(r point) point {
    39.     return point{p.i + r.i, p.j + r.j}
    41. }
    43. func (p point) at(grid [][]int) (int, bool) {
    44.     if p.i < 0 || p.i >= len(grid) {
    45.         return 0, false
    46.     }
    47.     if p.j < 0 || p.j >= len(grid[0]) {
    48.         return 0, false
    49.     }
    50.     return grid[p.i][p.j], true
    51. }
    53. func walk(maze [][]int, start, end point) [][]int {
    54.     steps := make([][]int, len(maze))
    55.     for i := range steps {
    56.         steps[i] = make([]int, len(maze[i]))
    57.     }
    59.     Q := []point{start}
    61.     for len(Q) > 0 {
    62.         cur := Q[0]
    63.         Q = Q[1:]
    65.         if cur == end {
    66.             break
    67.         }
    69.         for _, dir := range dirs {
    70.             next := cur.add(dir)
    72.             // 下个节点是空白的才能继续
    73.             val, ok := next.at(maze)
    74.             if !ok || val == 1 {
    75.                 continue
    76.             }
    78.             val, ok = next.at(steps)
    79.             if !ok || val != 0 {
    80.                 continue
    81.             }
    83.             if next == start {
    84.                 continue
    85.             }
    87.             curSteps, _ := cur.at(steps)
    88.             steps[next.i][next.j] = curSteps + 1
    90.             Q = append(Q, next)
    91.         }
    92.     }
    93.     return steps
    94. }
    96. func main() {
    97.     maze := readMaze("maze/maze.in")
    99.     steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})
    100.     for _, row := range steps {
    101.         for _, val := range row {
    102.             fmt.Printf("%3d ", val)
    103.         }
    104.         fmt.Println()
    105.     }
    106. }