广度优先搜索

Golang

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)
    fmt.Fscanln(file)
    for j := range maze[i] {

      fmt.Fscanf(file, "%d", &maze[i][j])
    }
  }
  return maze
}

type point struct {
  i, j int
}

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

var dirs = [4]point{
  {-1, 0},
  {0, -1},
  {1, 0},
  {0, 1},
}

func walk(maze [][]int, start, end point) [][]int {
  steps := make([][]int, len(maze))
  for i := range steps {
    steps[i] = make([]int, len(maze[i]))
  }
  Q := []point{start}

  for len(Q) > 0 {
    current := Q[0]
    Q = Q[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 {
        continue
      }

      if next == start {
        continue
      }

      currentSteps, _ := current.at(steps)

      steps[next.i][next.j] = currentSteps + 1

      Q = append(Q, next)
    }
  }

  return steps
}

func main() {
  maze := readMaze("src/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("%d  ", val)
    }
    fmt.Println()
  }
}