题目 #
You are given an m x n grid grid where:
- ‘.’ is an empty cell.
- ‘#’ is a wall.
- ‘@’ is the starting point.
- Lowercase letters represent keys.
- Uppercase letters represent locks.
You start at the starting point and one move consists of walking one space in one of the four cardinal directions. You cannot walk outside the grid, or walk into a wall.
If you walk over a key, you can pick it up and you cannot walk over a lock unless you have its corresponding key.
For some 1 <= k <= 6, there is exactly one lowercase and one uppercase letter of the first k letters of the English alphabet in the grid. This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys. If it is impossible, return -1.
思路1 #
分析 #
- 自己没想出来，使用官方解法
- 使用bfs可以计算点到其他点的距离
- 使用全排列将所有钥匙位置顺序给出来，使用bfs直接找所有方案步数，然后返回最小
代码实现 #
1type pointT struct {
2 x int
3 y int
4}
5
6var (
7 // 按照上下左右的相对位置设定，用于后面方便找四周的点
8 kRoundPoints = [][]int{
9 {0, -1},
10 {0, 1},
11 {-1, 0},
12 {1, 0},
13 }
14)
15
16func shortestPathAllKeys(grid []string) int {
17 // location['a'] is the (x, y) of a
18 location := make(map[byte]pointT)
19 for i := 0; i < len(grid); i++ {
20 for j := 0; j < len(grid[0]); j++ {
21 ch := grid[i][j]
22 if ch != '.' && ch != '#' {
23 location[ch] = pointT{j, i}
24 }
25 }
26 }
27 keyNums := len(location) / 2
28 // 枚举到所有的钥匙，题目条件只会从a-b、a-c、a-d、a-e、a-f几种情况
29 alphabet := make([]byte, keyNums)
30 for i := 0; i < keyNums; i++ {
31 alphabet[i] = byte('a' + i)
32 }
33
34 res := -1
35 permutation(alphabet, 0, func(str []byte) {
36 ans := 0
37 keymask := 0
38 for i := 0; i < len(str); i++ {
39 var src byte
40 if i == 0 {
41 src = '@'
42 } else {
43 src = alphabet[i-1]
44 }
45 tmp := bfs(location[src], location[alphabet[i]], grid, keymask)
46 if tmp == -1 {
47 return
48 }
49 ans += tmp
50 keymask |= 1 << (alphabet[i] - 'a')
51 }
52 if res == -1 || ans < res {
53 res = ans
54 }
55 })
56 return res
57}
58
59// 全排列
60func permutation(str []byte, index int, f func(str []byte)) {
61 if len(str) == index {
62 f(str)
63 return
64 }
65
66 // 不交换的场景
67 permutation(str, index+1, f)
68 // index对应位置向后交换
69 for i := index + 1; i < len(str); i++ {
70 str[i], str[index] = str[index], str[i]
71 permutation(str, index+1, f)
72 str[i], str[index] = str[index], str[i]
73 }
74}
75
76// 计算src到dst的最短路径长度，keymask为按位标记某个钥匙是否已找到
77// 返回从src到dst的最短路径长度
78func bfs(src pointT, dst pointT, grid []string, keymask int) int {
79 // 减小计算量，走过的路不再走，记录一下哪里走过了
80 seen := make([][]bool, len(grid))
81 for i := range seen {
82 seen[i] = make([]bool, len(grid[0]))
83 }
84 // 源地址记录走过了，注意x是第二维的坐标
85 seen[src.y][src.x] = true
86
87 // 使用层数作为步数
88 curDepth := 0
89 var queue list.List
90 // 插入源地址，作为第一层，使用nil作为层间隔
91 queue.PushBack(src)
92 queue.PushBack(nil)
93 // 队列一定含有一个层间隔，不在头就在尾，如果只剩一个层间隔，说明没路可走
94 for queue.Len() > 1 {
95 tmp := queue.Front().Value
96 queue.Remove(queue.Front())
97 if tmp == nil {
98 // 找到层间隔，说明当前层遍历完了，步数加一准备下一层
99 curDepth++
100 // 当前层遍历完，队列剩余的都是下一层，加入一个层间隔
101 queue.PushBack(nil)
102 continue
103 }
104
105 // 判断当前点是不是目标点，如果是，说明走到了，返回步数
106 tx, ty := tmp.(pointT).x, tmp.(pointT).y
107 if tx == dst.x && ty == dst.y {
108 return curDepth
109 }
110 // 不是目标点，从此点出发，向四周走一下
111 for i := range kRoundPoints {
112 px, py := tx+kRoundPoints[i][0], ty+kRoundPoints[i][1]
113 // 如果超出边界或者已经走过了或者碰到墙，就继续
114 if py < 0 || py >= len(grid) || px < 0 || px >= len(grid[0]) || seen[py][px] || grid[py][px] == '#' {
115 continue
116 }
117 ch := grid[py][px]
118 // 如果是锁，看一下有没有钥匙，没有钥匙就跳过
119 if (ch <= 'Z' && ch >= 'A') && ((1<<(ch-'A'))&keymask) == 0 {
120 continue
121 }
122 // 这个点可以走，走上去，记录到队列中，作为下一层的起点
123 seen[py][px] = true
124 queue.PushBack(pointT{px, py})
125 }
126 }
127 return -1
128}
思路2 #
分析 #
- 来自网上其他网友的方案，使用bfs，但是将状态加到bfs判断中，也就是三维的bfs
代码 #
1type pointST struct {
2 x int
3 y int
4 step int
5 state int
6}
7
8func shortestPathAllKeys1(grid []string) int {
9 // location['a'] is the (x, y) of a
10 location := make(map[byte]pointST)
11 for i := 0; i < len(grid); i++ {
12 for j := 0; j < len(grid[0]); j++ {
13 ch := grid[i][j]
14 if ch != '.' && ch != '#' {
15 location[ch] = pointST{j, i, 0, 0}
16 }
17 }
18 }
19 keyNums := len(location) / 2
20 finalState := (1 << keyNums) - 1
21
22 // 将钥匙的持有状态作为判断成三维的bfs
23 return bfsThree(location['@'], grid, finalState)
24}
25
26// 将钥匙的持有状态作为判断成三维的bfs
27func bfsThree(src pointST, grid []string, finalState int) int {
28 sx, sy := src.x, src.y
29
30 // 减小计算量，走过的路不再走，记录一下哪里走过了
31 seen := make([][][]bool, len(grid))
32 for i := range seen {
33 seen[i] = make([][]bool, len(grid[0]))
34 for j := range seen[i] {
35 seen[i][j] = make([]bool, finalState+1)
36 }
37 }
38 seen[sy][sx][0] = true
39
40 var queue list.List
41 queue.PushBack(src)
42 for queue.Len() > 0 {
43 tmp := queue.Front().Value
44 queue.Remove(queue.Front())
45
46 // 判断当前点是不是已经达成目标
47 tx, ty, step, state := tmp.(pointST).x, tmp.(pointST).y, tmp.(pointST).step, tmp.(pointST).state
48 if state == finalState {
49 return step
50 }
51 // 不是目标点，从此点出发，向四周走一下
52 for i := range kRoundPoints {
53 px, py := tx+kRoundPoints[i][0], ty+kRoundPoints[i][1]
54 // 如果超出边界或者碰到墙，就继续
55 if py < 0 || py >= len(grid) || px < 0 || px >= len(grid[0]) || grid[py][px] == '#' {
56 continue
57 }
58 // 判断是否曾以相同状态要走过这个点
59 if seen[py][px][state] {
60 continue
61 }
62 ch := grid[py][px]
63 // 如果是锁，看一下有没有钥匙，没有钥匙就跳过
64 if (ch <= 'Z' && ch >= 'A') && ((1<<(ch-'A'))&state) == 0 {
65 continue
66 }
67 // 可以踩上去，就记录踩上去前的状态
68 seen[py][px][state] = true
69 // 如果是钥匙，保存新的状态到队列中
70 tmpState := state
71 if ch <= 'z' && ch >= 'a' {
72 tmpState |= (1 << (ch - 'a'))
73 }
74 // 记录到队列中，作为下一层的点
75 queue.PushBack(pointST{px, py, step + 1, tmpState})
76 }
77 }
78 return -1
79}
思路3 #
分析 #
- 来自官方的方案，将每个钥匙和key都作为关键点，计算出所有关键点之间的距离（不解锁）
- 相当于如果要从a解锁A到达b，那么关键点就是
a -> A+A -> b，而不是a到b - 计算出来之后，这个map进行Dijkastra算法，计算到达某个状态下的最低步数
代码 #
1type pointTT struct {
2 x int
3 y int
4 step int
5 state int
6}
7
8type littleQueue []pointTT
9
10func (q *littleQueue) Push(v interface{}) {
11 *q = append(*q, v.(pointTT))
12}
13func (q *littleQueue) Pop() interface{} {
14 x := (*q)[len(*q)-1]
15 *q = (*q)[:len(*q)-1]
16 return x
17}
18func (q *littleQueue) Len() int { return len(*q) }
19func (q *littleQueue) Less(i, j int) bool { return (*q)[i].step < (*q)[j].step }
20func (q *littleQueue) Swap(i, j int) { (*q)[i], (*q)[j] = (*q)[j], (*q)[i] }
21
22func shortestPathAllKeys2(grid []string) int {
23 location := make(map[byte]pointTT)
24 // 小根堆，用于Djikastra算法
25 pq := make(littleQueue, 0, 1)
26 // 距离矩阵，保存每个点到其他关键点的距离
27 distMaps := make(map[byte]map[byte]int)
28 heap.Init(&pq)
29 for i := 0; i < len(grid); i++ {
30 for j := 0; j < len(grid[0]); j++ {
31 ch := grid[i][j]
32 if ch != '.' && ch != '#' {
33 p := pointTT{j, i, 0, 0}
34 location[ch] = p
35 distMaps[ch] = bpfFrom(p, grid)
36 }
37 if ch == '@' {
38 heap.Push(&pq, pointTT{j, i, 0, 0})
39 }
40 }
41 }
42 keyNums := len(location) / 2
43 finalState := (1 << keyNums) - 1
44
45 finalDistMap := make(map[string]int)
46 finalDistMap[fmt.Sprintf("%c%d", '@', 0)] = 0
47
48 // Dijkstra算法
49 for pq.Len() > 0 {
50 // 每次取队列中最小的距离
51 p := heap.Pop(&pq).(pointTT)
52 // finalState还是队列中最小的步数，说明已经到了最小的步数
53 if p.state == finalState {
54 return p.step
55 }
56 // 从此点开始走，找到所有关键点
57 ch := grid[p.y][p.x]
58 distMap := distMaps[ch]
59 for i, v := range distMap {
60 state := p.state
61 if i >= 'A' && i <= 'Z' {
62 // 走到锁，判断是否可以走，不可以走就不走
63 if (state & (1 << (i - 'A'))) == 0 {
64 continue
65 }
66 } else if i >= 'a' && i <= 'z' {
67 // 走到钥匙，拿起钥匙
68 state |= (1 << (i - 'a'))
69 }
70 // 能走的点，如果没到达过，或者到达过但比之前距离更短，才加入队列
71 t := location[i]
72 t.state = state
73 t.step = p.step + v
74 key := fmt.Sprintf("%c%d", i, state)
75 if d, ok := finalDistMap[key]; ok && t.step >= d {
76 continue
77 }
78 finalDistMap[key] = t.step
79 heap.Push(&pq, t)
80 }
81 }
82 return -1
83}
84
85func bpfFrom(src pointTT, grid []string) map[byte]int {
86 result := make(map[byte]int)
87 sx, sy := src.x, src.y
88 // 减小计算量，走过的路不再走，记录一下哪里走过了
89 seen := make([][]bool, len(grid))
90 for i := range seen {
91 seen[i] = make([]bool, len(grid[0]))
92 }
93 seen[sy][sx] = true
94
95 var queue list.List
96 queue.PushBack(src)
97 for queue.Len() > 0 {
98 t := queue.Front().Value.(pointTT)
99 queue.Remove(queue.Front())
100
101 // 向四周走一次
102 for i := range kRoundPoints {
103 px, py := t.x+kRoundPoints[i][0], t.y+kRoundPoints[i][1]
104 // 如果超出边界或者碰到墙或者走过了，就继续
105 if py < 0 || py >= len(grid) || px < 0 || px >= len(grid[0]) || seen[py][px] || grid[py][px] == '#' {
106 continue
107 }
108 // 判断是否是空位，空位就继续走
109 seen[py][px] = true
110 ch := grid[py][px]
111 if ch == '.' {
112 // 记录到队列中，作为下一层的点
113 queue.PushBack(pointTT{px, py, t.step + 1, 0})
114 continue
115 }
116 // 关键点插入map，这个时候还没走上去，所以步数+1才走上去
117 result[ch] = t.step + 1
118 }
119 }
120 return result
121}