给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。

最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。

请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。

数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。

输入格式

第一行包含两个整数n和m。

接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。

输出格式

输出一个整数，表示从左上角移动至右下角的最少移动次数。

数据范围

1≤n,m≤100

输入样例：

5 5
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0

输出样例：

8

Go 代码

package main

import "fmt"

type pair struct {
    first, second int
}

var g [][]int // 存储地图
var d [][]int // 每个点到起点的距离
var n, m int

func bfs() int {
    q := make([]pair, 0)
    q = append(q, pair{0, 0})
    dx := []int{-1, 0, 1, 0} // 向量表示向上或向下
    dy := []int{0, 1, 0, -1} // 向量表示向左或向右
    for len(q) > 0 {
        t := q[0] // 取出队头元素
        q = q[1:]
        a, b := t.first, t.second
        for i := 0; i < 4; i++ { // 枚举4个方向
            lx := a + dx[i] // 表示沿着这个方向走
            ly := b + dy[i] // 可以走到哪个点
            // 没有走出边界，并且是没有走过
            if lx >= 0 && lx < n && ly >= 0 && ly < m && g[lx][ly] == 0 && d[lx][ly] == -1 {
                d[lx][ly] = d[a][b] + 1     // 记录到这点的距离
                q = append(q, pair{lx, ly}) // 并把这点记录进队列
            }
        }
    }
    return d[n-1][m-1] // 输出右下角点的距离
}

func main() {
    fmt.Scanf("%d%d", &n, &m)
    g = make([][]int, n)
    d = make([][]int, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, m)
        d[i] = make([]int, m)
        for j := 0; j < m; j++ {
            fmt.Scanf("%d", &g[i][j]) // 读入地图
            d[i][j] = -1              // 初始化为 -1 表示没有走过
        }
    }
    d[0][0] = 0 // 表示0，0位置已经走过了

    fmt.Printf("%d", bfs())
}

Go 代码 记录路径

package main

import "fmt"

type pair struct {
    first, second int
}

var g [][]int // 存储地图
var d [][]int // 每个点到起点的距离
var n, m int
var prev [][]pair

func bfs() int {
    q := make([]pair, 0)
    q = append(q, pair{0, 0})
    dx := []int{-1, 0, 1, 0} // 向量表示向上或向下
    dy := []int{0, 1, 0, -1} // 向量表示向左或向右
    for len(q) > 0 {
        t := q[0] // 取出队头元素
        q = q[1:]
        a, b := t.first, t.second
        for i := 0; i < 4; i++ { // 枚举4个方向
            lx := a + dx[i] // 表示沿着这个方向走
            ly := b + dy[i] // 可以走到哪个点
            // 没有走出边界，并且是没有走过
            if lx >= 0 && lx < n && ly >= 0 && ly < m && g[lx][ly] == 0 && d[lx][ly] == -1 {
                d[lx][ly] = d[a][b] + 1 // 记录到这点的距离
                prev[lx][ly] = t
                q = append(q, pair{lx, ly}) // 并把这点记录进队列
            }
        }
    }
    x, y := n-1, m-1
    for x > 0 || y > 0 {
        fmt.Print(x, " ", y, "\n")
        t := prev[x][y]
        x, y = t.first, t.second
    }
    fmt.Println()
    return d[n-1][m-1] // 输出右下角点的距离
}

func main() {
    fmt.Scanf("%d%d", &n, &m)
    g = make([][]int, n)
    d = make([][]int, n)
    prev = make([][]pair, n)
    for i := 0; i < n; i++ {
        g[i] = make([]int, m)
        d[i] = make([]int, m)
        prev[i] = make([]pair, m)
        for j := 0; j < m; j++ {
            fmt.Scanf("%d", &g[i][j]) // 读入地图
            d[i][j] = -1              // 初始化为 -1 表示没有走过
        }
    }
    d[0][0] = 0 // 表示0，0位置已经走过了

    fmt.Printf("%d", bfs())
}