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 <= grid.length <= 301 <= grid[0].length <= 30grid[i][j]contains only'.','#','@','a'-'f'and'A'-'F'- The number of keys is in
[1, 6]. Each key has a different letter and opens exactly one lock.
题目大意 #
给定一个二维网格 grid。 “.” 代表一个空房间， “#” 代表一堵墙， “@” 是起点，（“a”, “b”, …）代表钥匙，（“A”, “B”, …）代表锁。
我们从起点开始出发，一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。
假设 K 为钥匙/锁的个数，且满足 1 <= K <= 6，字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。
返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，返回 -1 。
提示：
- 1 <= grid.length <= 30
- 1 <= grid[0].length <= 30
- grid[i][j] 只含有 ‘.’, ‘#’, ‘@’, ‘a’-‘f’ 以及 ‘A’-‘F’
- 钥匙的数目范围是 [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
}