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代码](https://github.com/algorithmzuo/coding-for-great-offer/blob/main/src/class42/Problem_0265_PaintHouseII.java)
