2022-01-31：迷宫 III。 由空地和墙组成的迷宫中有一个球。球可以向上（u）下（d）左（l）右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中还有一个洞，当球运动经过洞时，就会掉进洞里。 给定球的起始位置，目的地和迷宫，找出让球以最短距离掉进洞里的路径。 距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。通过'u', 'd', 'l' 和 'r'输出球的移动方向。 由于可能有多条最短路径， 请输出字典序最小的路径。如果球无法进入洞，输出"impossible"。 迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。 力扣499。

答案2022-01-31：

宽度优先遍历。每走一步，都需要记录一下。

代码用golang编写。代码如下：

package main

import "fmt"

func main() {
    maze := [][]int{
        {0, 0, 0, 0, 0},
        {1, 1, 0, 0, 1},
        {0, 0, 0, 0, 0},
        {0, 1, 0, 0, 1},
        {0, 1, 0, 0, 0},
    }
    ball := []int{4, 3}
    hole := []int{0, 1}
    ret := findShortestWay(maze, ball, hole)
    fmt.Println(ret)
}

// 节点：来到了哪？(r,c)这个位置
// 从哪个方向来的！d -> 0 1 2 3 4
// 之前做了什么决定让你来到这个位置。
type Node struct {
    r int
    c int
    d int
    p string
}

func NewNode(row, col, dir0 int, path0 string) *Node {
    ans := &Node{}
    ans.r = row
    ans.c = col
    ans.d = dir0
    ans.p = path0
    return ans
}

func findShortestWay(maze [][]int, ball, hole []int) string {
    n := len(maze)
    m := len(maze[0])
    q1 := make([]*Node, n*m)
    q2 := make([]*Node, n*m)
    s1 := 0
    s2 := 0
    visited := make([][][]bool, len(maze))
    for i := 0; i < len(maze); i++ {
        visited[i] = make([][]bool, len(maze[0]))
        for j := 0; j < len(maze[0]); j++ {
            visited[i][j] = make([]bool, 4)
        }
    }
    s1 = spread(maze, n, m, NewNode(ball[0], ball[1], 4, ""), visited, q1, s1)
    for s1 != 0 {
        for i := 0; i < s1; i++ {
            cur := q1[i]
            if hole[0] == cur.r && hole[1] == cur.c {
                return cur.p
            }
            s2 = spread(maze, n, m, cur, visited, q2, s2)
        }
        tmp := q1
        q1 = q2
        q2 = tmp
        s1 = s2
        s2 = 0
    }
    return "impossible"
}

var to = [][]int{{1, 0}, {0, -1}, {0, 1}, {-1, 0}, {0, 0}}

var re = []string{"d", "l", "r", "u"}

// maze迷宫，走的格子
// n 行数
// m 列数
// 当前来到的节点，cur -> (r,c) 方向 路径（决定）
// v [行][列][方向] 一个格子，其实在宽度有限遍历时，是4个点！
// q 下一层的队列
// s 下一层队列填到了哪，size
// 当前点cur，该分裂分裂，该继续走继续走，所产生的一下层的点，进入q，s++
// 返回值：q增长到了哪？返回size -> s
func spread(maze [][]int, n, m int, cur *Node, v [][][]bool, q []*Node, s int) int {
    d := cur.d
    r := cur.r + to[d][0]
    c := cur.c + to[d][1]
    // 分裂去！
    if d == 4 || r < 0 || r == n || c < 0 || c == m || maze[r][c] != 0 {
        for i := 0; i < 4; i++ {
            if i != d {
                r = cur.r + to[i][0]
                c = cur.c + to[i][1]
                if r >= 0 && r < n && c >= 0 && c < m && maze[r][c] == 0 && !v[r][c][i] {
                    v[r][c][i] = true
                    next := NewNode(r, c, i, cur.p+re[i])
                    q[s] = next
                    s++
                }
            }
        }
    } else { // 不分裂！继续走！
        if !v[r][c][d] {
            v[r][c][d] = true
            q[s] = NewNode(r, c, d, cur.p)
            s++
        }
    }
    return s
}

执行结果如下： 图片

左神java代码