leetcode 865 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. 这道题就像我在498题中说的迷宫问题一样，求到达某点的最短路径，显然是用bfs
  2. 那么这和普通的bfs有什么不同呢，现在给出一个具体实例[[@…a],[.###A],[b.BCc]]，你会发现这里要走回头路的，那么如果凭空就可以来回走的话，会是一个死循环，但我们稍微仔细思考一下，我认为想到走回头路的条件是获得一个新key这个点应该不难想到，那么我们只需要将标准bfs写法中的visited中key值变为(i,j,key)即可
  3. 虽然我做出来了，但是我的代码目前比较凌乱（因为经过多次修改），现在借助一位老哥的代码，和我的思路是完全一样的，来看一看具体如何实现

思路：

  1. 首先遍历一次数组，记录下起始位置，即‘@’，以及key的数量，即小写字母的数量，记为numOfKey
  2. 队列中的每项元素具有如下结构(i,j,step,key,collectedkey):
    1. i,j表示位置,step代表bfs的深度
    2. key代表目前能走的格子从，初始化为'abcdef.@'，每收集到一个小写字母便将对应的大写字母加入key中
    3. collectedkey代表已经收集的key的数量，如果collectedkey = numOfKey，则代表成功
  3. 用visited记录已经走过的状态，避免无限循环，visited中值为(i,j,key)，保证只有在收集到新key之后才能走回头路
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution(object):
    def shortestPathAllKeys(self, grid):
        """
        :type grid: List[str]
        :rtype: int
        """
        n, m = len(grid), len(grid[0])
        numOfKeys = 0
        direc = [[0,1],[0,-1],[1,0],[-1,0]]
        visited = set()
        
        for i in range(n):
            for j in range(m):
                if grid[i][j] == '@':
                    starti = i
                    startj = j
                elif grid[i][j] in "abcdef":
                    numOfKeys += 1
        
        deque = collections.deque()
        deque.append([starti, startj, 0, ".@abcdef", 0])
        
        while deque:
            i, j, steps, keys, collectedKeys = deque.popleft()

            if grid[i][j] in "abcdef" and grid[i][j].upper() not in keys:
                keys += grid[i][j].upper()
                collectedKeys += 1
            
            if collectedKeys == numOfKeys:
                return steps

            for x, y in direc:
                ni = i+x
                nj = j+y
                if 0<=ni<n and 0<=nj<m and grid[ni][nj] in keys:
                    if (ni, nj, keys) not in visited:
                        visited.add((ni,nj,keys))
                        deque.append([ni, nj, steps + 1, keys, collectedKeys])
                
        return -1


35 / 35 test cases passed.
difficulty: hard
Runtime: 504 ms