广度优先算法走迷宫

记录一个demo，方便以后查阅

package main

import (
    "fmt"
    "os"
)

type point struct {
    i, j int
}

func main() {
    //读取文件
    file, err := os.Open("./maze.in")
    defer file.Close()
    if err != nil {
        fmt.Errorf("read file fail: %v", err)
    }
    //获取迷宫地图的规格
    var row, col int
    fmt.Fscanf(file, "%d %d", &row, &col)
    //读取迷宫地图
    var maze = make([][]int, row)
    for i := range maze {
        maze[i] = make([]int, col)
        for j, val := range maze[i] {
            fmt.Fscanf(file, "%d", &val)
            maze[i][j] = val
        }
    }
    //生成一个迷宫路线图steps
    var steps = make([][]int, len(maze))
    for i := range steps {
        steps[i] = make([]int, len(maze[i]))
    }
    //定义起始位置和结束位置
    start := point{0, 0}
    end := point{len(maze) - 1, len(maze[0]) - 1}
    //定义方向向量 逆时针（上左下右）
    direction := []point{
        {-1, 0},
        {0, -1},
        {1, 0},
        {0, 1},
    }
    //探索起始点，发现下一步
    var Q []point
    Q = append(Q, start)
    for {
        origin := Q[0]
        Q = Q[1:]
        //判断是否探索到终点
        if origin == end {
            break
        }
        //逆时针方向探索队列中取出的点
        for _, d := range direction {
            next := point{origin.i + d.i, origin.j + d.j}
            //判断是否越界
            if next.i < 0 || next.i >= len(maze) {
                continue
            }
            if next.j < 0 || next.j >= len(maze[0]) {
                continue
            }
            //判断是否为起始位置或者为墙壁
            if next == start || maze[next.i][next.j] == 1 {
                continue
            }
            //判断是否已经探索过
            if steps[next.i][next.j] != 0 {
                continue
            }
            //画出路线图
            steps[next.i][next.j] = steps[origin.i][origin.j] + 1
            //把新发现的点加入队列中等待探索
            Q = append(Q, next)
        }
    }
    //打印线路结果
    for _, step := range steps {
        for _, v := range step {
            fmt.Printf("%3d", v)
        }
        fmt.Println()
    }
}