0864. Shortest Path to Get All Keys

# 864. Shortest Path to Get All Keys#

## 题目 #

We are given a 2-dimensional `grid``"."` is an empty cell, `"#"` is a wall, `"@"` is the starting point, (`"a"``"b"`, …) are keys, and (`"A"``"B"`, …) are locks.

We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions. We cannot walk outside the grid, or walk into a wall. If we walk over a key, we pick it up. We can’t walk over a lock unless we have the 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’s impossible, return `-1`.

Example 1:

``````Input: ["@.a.#","###.#","b.A.B"]
Output: 8
``````

Example 2:

``````Input: ["@..aA","..B#.","....b"]
Output: 6
``````

Note:

1. `1 <= grid.length <= 30`
2. `1 <= grid[0].length <= 30`
3. `grid[i][j]` contains only `'.'``'#'``'@'``'a'-'f'` and `'A'-'F'`
4. The number of keys is in `[1, 6]`. Each key has a different letter and opens exactly one lock.

## 题目大意 #

1. 1 <= grid.length <= 30
2. 1 <= grid[0].length <= 30
3. grid[i][j] 只含有 ‘.’, ‘#’, ‘@’, ‘a’-‘f’ 以及 ‘A’-‘F’
4. 钥匙的数目范围是 [1, 6]，每个钥匙都对应一个不同的字母，正好打开一个对应的锁。

## 解题思路 #

• 给出一个地图，在图中有钥匙和锁，当锁在没有钥匙的时候不能通行，问从起点 @ 开始，到最终获得所有钥匙，最短需要走多少步。
• 这一题可以用 BFS 来解答。由于钥匙的种类比较多，所以 visited 数组需要 3 个维度，一个是 x 坐标，一个是 y 坐标，最后一个是当前获取钥匙的状态。每把钥匙都有获取了和没有获取两种状态，题目中说最多有 6 把钥匙，那么排列组合最多是 2^6 = 64 种状态。用一个十进制数的二进制位来压缩这些状态，二进制位分别来表示这些钥匙是否已经获取了。既然钥匙的状态可以压缩，其实 x 和 y 的坐标也可以一并压缩到这个数中。BFS 中存的数字是坐标 + 钥匙状态的状态。在 BFS 遍历的过程中，用 visited 数组来过滤遍历过的情况，来保证走的路是最短的。其他的情况无非是判断锁的状态，是否能通过，判断钥匙获取状态。
• 这一题不知道是否能用 DFS 来解答。我实现了一版，但是在 18 / 35 这组 case 上超时了，具体 case 见测试文件第一个 case。

## 代码 #

``````
package leetcode

import (
"math"
"strings"
)

// 解法一 BFS，利用状态压缩来过滤筛选状态
func shortestPathAllKeys(grid []string) int {
if len(grid) == 0 {
return 0
}
board, visited, startx, starty, res, fullKeys := make([][]byte, len(grid)), make([][][]bool, len(grid)), 0, 0, 0, 0
for i := 0; i < len(grid); i++ {
board[i] = make([]byte, len(grid[0]))
}
for i, g := range grid {
board[i] = []byte(g)
for _, v := range g {
if v == 'a' || v == 'b' || v == 'c' || v == 'd' || v == 'e' || v == 'f' {
fullKeys |= (1 << uint(v-'a'))
}
}
if strings.Contains(g, "@") {
startx, starty = i, strings.Index(g, "@")
}
}
for i := 0; i < len(visited); i++ {
visited[i] = make([][]bool, len(board[0]))
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
visited[i][j] = make([]bool, 64)
}
}
queue := []int{}
queue = append(queue, (starty<<16)|(startx<<8))
visited[startx][starty][0] = true
for len(queue) != 0 {
qLen := len(queue)
for i := 0; i < qLen; i++ {
state := queue[0]
queue = queue[1:]
starty, startx = state>>16, (state>>8)&0xFF
keys := state & 0xFF
if keys == fullKeys {
return res
}
for i := 0; i < 4; i++ {
newState := keys
nx := startx + dir[i][0]
ny := starty + dir[i][1]
if !isInBoard(board, nx, ny) {
continue
}
if board[nx][ny] == '#' {
continue
}
flag, canThroughLock := keys&(1<<(board[nx][ny]-'A')), false
if flag != 0 {
canThroughLock = true
}
if isLock(board, nx, ny) && !canThroughLock {
continue
}
if isKey(board, nx, ny) {
newState |= (1 << (board[nx][ny] - 'a'))
}
if visited[nx][ny][newState] {
continue
}
queue = append(queue, (ny<<16)|(nx<<8)|newState)
visited[nx][ny][newState] = true
}
}
res++
}
return -1
}

// 解法二 DFS，但是超时了，剪枝条件不够强
func shortestPathAllKeys1(grid []string) int {
if len(grid) == 0 {
return 0
}
board, visited, startx, starty, res, fullKeys := make([][]byte, len(grid)), make([][][]bool, len(grid)), 0, 0, math.MaxInt64, 0
for i := 0; i < len(grid); i++ {
board[i] = make([]byte, len(grid[0]))
}
for i, g := range grid {
board[i] = []byte(g)
for _, v := range g {
if v == 'a' || v == 'b' || v == 'c' || v == 'd' || v == 'e' || v == 'f' {
fullKeys |= (1 << uint(v-'a'))
}
}
if strings.Contains(g, "@") {
startx, starty = i, strings.Index(g, "@")
}
}
for i := 0; i < len(visited); i++ {
visited[i] = make([][]bool, len(board[0]))
}
for i := 0; i < len(board); i++ {
for j := 0; j < len(board[0]); j++ {
visited[i][j] = make([]bool, 64)
}
}
searchKeys(board, &visited, fullKeys, 0, (starty<<16)|(startx<<8), &res, []int{})
if res == math.MaxInt64 {
return -1
}
return res - 1
}

func searchKeys(board [][]byte, visited *[][][]bool, fullKeys, step, state int, res *int, path []int) {
y, x := state>>16, (state>>8)&0xFF
keys := state & 0xFF

if keys == fullKeys {
*res = min(*res, step)
return
}

flag, canThroughLock := keys&(1<<(board[x][y]-'A')), false
if flag != 0 {
canThroughLock = true
}
newState := keys
//fmt.Printf("x = %v y = %v fullKeys = %v keys = %v step = %v res = %v path = %v state = %v\n", x, y, fullKeys, keys, step, *res, path, state)
if (board[x][y] != '#' && !isLock(board, x, y)) || (isLock(board, x, y) && canThroughLock) {
if isKey(board, x, y) {
newState |= (1 << uint(board[x][y]-'a'))
}
(*visited)[x][y][newState] = true
path = append(path, x)
path = append(path, y)

for i := 0; i < 4; i++ {
nx := x + dir[i][0]
ny := y + dir[i][1]
if isInBoard(board, nx, ny) && !(*visited)[nx][ny][newState] {
searchKeys(board, visited, fullKeys, step+1, (ny<<16)|(nx<<8)|newState, res, path)
}
}
(*visited)[x][y][keys] = false
path = path[:len(path)-1]
path = path[:len(path)-1]
}
}

func isLock(board [][]byte, x, y int) bool {
if (board[x][y] == 'A') || (board[x][y] == 'B') ||
(board[x][y] == 'C') || (board[x][y] == 'D') ||
(board[x][y] == 'E') || (board[x][y] == 'F') {
return true
}
return false
}

func isKey(board [][]byte, x, y int) bool {
if (board[x][y] == 'a') || (board[x][y] == 'b') ||
(board[x][y] == 'c') || (board[x][y] == 'd') ||
(board[x][y] == 'e') || (board[x][y] == 'f') {
return true
}
return false
}

``````

Sep 6, 2020