读取的文件

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

实现代码

package main

import (
    "fmt"
    "os"
)

// 读取文件的时候,注意win下回车换行是\r\n
func readMaze(filename string) [][]int {
    file, err := os.Open(filename)
    if err != nil {
        panic(err)
    }

    var row, col int
    var end string

    // 读取一行,遇到换行符停止读取; end 把回车读取; 遇到空格跳过,遇到换行停止,就是取一行数据
    fmt.Fscanf(file, "%d %d %s", &row, &col, &end)

    // 二维数组(slice),row=6,代表 一维数组里面还有6个数组  [[] [] [] [] [] []]
    maze := make([][]int, row) 

    for i := range maze {
        maze[i] = make([]int, col) // 二维数组里面的每个数组,也有5个int值

        // 取出行
        for j := range maze[i] {
            fmt.Fscanf(file, "%d", &maze[i][j]) //每次读一个数字,循环读取一行
        }

        fmt.Fscanf(file, "%d", &end) // 一列取出后,行末的换行符也取出来
    }

    return maze
}

type point struct {
    i, j int
}

// 方向,上 左 下 右
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) {
    // 如果行小于0 或者 行数操作最大行数
    if p.i < 0 || p.i >= len(grid) {
        return 0, false
    }

    // 如果列数小于0 或者 列数 超过本行最大列数
    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 {
    steps := make([][]int, len(maze))
    for i := range steps {
        steps[i] = make([]int, len(maze[i]))
    }

    // 记录走到哪里,哪些地方还要走
    Q := []point{start} // [{0 0}]

    for len(Q) > 0 {
        cur := Q[0]
        Q = Q[1:]

        if cur == end {
            break
        }

        // 循环4个方向,分别走四个方向
        for _, dir := range dirs {
            next := cur.add(dir)

            val, ok := next.at(maze)

            // 1 撞墙了
            if !ok || val == 1 {
                continue
            }

            // val 不等于0, 说明走过了
            val, _ = 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 walkPath(steps [][]int, start point, end point) []point {
    paths := []point{start}
    // 记录走到哪里,哪些地方还要走
    Q := []point{start} // [{0 0}]

    for len(Q) > 0  {
        cur := Q[0]
        Q = Q[1:]

        if cur == end {
            break
        }

        for _, dir := range dirs {
            prve := cur.add(dir)
            val, ok := prve.at(steps)
            if !ok {
                continue
            }

            // 如果找到上一步, 把上一部记录到paths,并且把上一步记录到Q,下次继续走
            if val + 1 == steps[cur.i][cur.j] {
                paths = append(paths, prve)
                Q = append(Q, prve)
            }
        }
    }

    return paths
}

// 入口函数
func main() {
    maze := readMaze("maze/maze.in")

    // 读取文件后,打印文件
    for _, row := range maze {
        for _, val := range row {
            fmt.Printf("%3d", val)
        }
        fmt.Println()
    }

    fmt.Println()

    // 开始走迷宫
    steps := walk(maze, point{0, 0}, point{len(maze) - 1, len(maze[0]) - 1})

    for _, row := range steps {
        for _, val := range row {
            fmt.Printf("%3d", val)
        }
        fmt.Println()
    }

    fmt.Println()
    fmt.Printf("迷宫至少要走%d步", steps[len(steps)-1][len(steps[0])-1]+1)

    fmt.Println()

    // 迷宫走完,从后往前获取走过的路径
    paths := walkPath(steps, point{len(steps) - 1, len(steps[0]) - 1}, point{0, 0})
    fmt.Println()
    fmt.Printf("走的每一个点:%d", paths)
}