题目描述
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 <= 30
1 <= grid[0].length <= 30
grid[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
(BFS)
题解:因为钥匙数很少,所以可以采取暴力枚举每一种可能的获取钥匙的顺序情况。我们使用三维数组dist[x][y][st]
来表示当前位置在(x,y)
并且当前手上的钥匙为st
,st
是使用状态压缩的思想来保存六把钥匙的状态的。
首先我们遍历整个数组,找到起点位置,和总共有多少把锁。并把起点位置的状态加入队列,接下来执行BFS,对上下左右四个合法的方向开始走(不越界,不是墙,不是没有锁的门),如果得到了一个更优的步数,那么更新步数并将这个点加入堆,直至我们搜到了所有的钥匙,或者堆为空(没有找到一个合法的路径)。
class Solution {
public:
struct st{
int x,y,keys;
st(){}
st(int x,int y,int keys):x(x),y(y),keys(keys){}
};
int shortestPathAllKeys(vector<string>& grid) {
int n = grid.size(),m = grid[0].size(),cnt = 0;
int dist[n][m][1 << 6],dx[4] = {-1,0,1,0},dy[4] = {0,1,0,-1};
memset(dist,0x3f3f3f3f,sizeof(dist));
queue<st> q;
for(int i = 0 ; i < n ; i ++)
{
for(int j = 0 ; j < m ; j ++)
{
if(grid[i][j] == '@')
{
q.push(st(i,j,0));
dist[i][j][0] = 0;
}
else if(grid[i][j] >= 'A' && grid[i][j] <= 'F')
cnt ++;
}
}
while(!q.empty())
{
auto t = q.front();
q.pop();
for(int i = 0 ; i < 4 ; i ++)
{
int x = t.x + dx[i],y = t.y + dy[i];
if(x < 0 || x >= n || y < 0 || y >= m || grid[x][y] == '#')
continue;
char ch = grid[x][y];
if(ch >= 'A' && ch <= 'F' && ((t.keys >> (ch - 'A')) & 1) == 0)
continue;
int next_keys = t.keys;
if(ch >= 'a' && ch <= 'f')
next_keys = next_keys | (1 << ch - 'a');
if(dist[x][y][next_keys] > dist[t.x][t.y][t.keys] + 1)
{
dist[x][y][next_keys] = dist[t.x][t.y][t.keys] + 1;
q.push(st(x,y,next_keys));
if(next_keys == (1 << cnt) - 1)
return dist[x][y][next_keys];
}
}
}
return -1;
}
};