带压缩的额外状态的 BFS

  |  

摘要: 带压缩的额外状态的 BFS

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:潮汐朝夕
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings


本文我们看一个比较难的 BFS 的问题。说的是我们在二维矩阵上走迷宫,其中除了常规的道路和墙,还有钥匙和锁,因此搜索过程中需要维护比较复杂的状态。


题目

864. 获取所有钥匙的最短路径

给定一个二维网格 grid。 “.” 代表一个空房间, “#” 代表一堵墙, “@” 是起点,(”a”, “b”, …)代表钥匙,(”A”, “B”, …)代表锁。

我们从起点开始出发,一次移动是指向四个基本方向之一行走一个单位空间。我们不能在网格外面行走,也无法穿过一堵墙。如果途经一个钥匙,我们就把它捡起来。除非我们手里有对应的钥匙,否则无法通过锁。

假设 K 为钥匙/锁的个数,且满足 1 <= K <= 6,字母表中的前 K 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之,每个锁有唯一对应的钥匙,每个钥匙也有唯一对应的锁。另外,代表钥匙和锁的字母互为大小写并按字母顺序排列。

返回获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙,返回 -1 。

示例 1:
输入:[“@.a.#”,”###.#”,”b.A.B”]
输出:8

示例 2:
输入:[“@..aA”,”..B#.”,”….b”]
输出:6

题解

算法:带压缩的额外状态的 BFS

在常规的用 BFS 解决走迷宫问题的算法中,每走一步,我们都记录所到位置的横纵坐标以及步数。

而本题中我们只有在有对应钥匙的情况下才能通过有锁的位置,因此还需要记录各个锁的持有状态,

因为钥匙和锁的数量很少,可以用状态压缩记录锁的情况,用一个整数 key_state 表示,key_state 的各个位表示对应的钥匙是否已经取到。

这样在 BFS 的队列里的内容除了节点编号(矩阵的话就是(x, y))和步数 step 以外,还有一个可以压缩的状态 key_state,如下图:

代码(c++)

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
struct State
{
int x, y;
int key_state;
int step;
State(int x, int y, int key_state, int step):x(x),y(y),key_state(key_state),step(step){}
};

class Solution {
public:
// 状态压缩BFS
int shortestPathAllKeys(vector<string>& grid) {
// 1 <= k <= 6
// 111111
// BFS 过程中,q.pop() 出新点 cur,先 check key_state 是否全1
// 然后四周点压入 visited[x][y][state] 记录
int n = grid.size(), m = grid[0].size();
State start(-1, -1, 0, 0);
int key_num = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
{
if(grid[i][j] == '@')
{
start.x = i;
start.y = j;
}
if(grid[i][j] >= 'a' && grid[i][j] <= 'f')
++key_num;
}
queue<State> q;
q.push(start);
vector<vector<vector<bool> > > visited(n, vector<vector<bool> >(m, vector<bool>((1 << key_num), false)));
visited[start.x][start.y][0] = true;
while(!q.empty())
{
State cur = q.front();
q.pop();
if(_check(key_num, cur.key_state))
return cur.step;
for(int d = 0; d < 4; ++d)
{
int x = cur.x + dx[d], y = cur.y + dy[d];
if(x < 0 || x >= n || y < 0 || y >= m) continue;
if(grid[x][y] == '#') continue;
if(grid[x][y] >= 'A' && grid[x][y] <= 'F' && !((1 << (grid[x][y] - 'A')) & cur.key_state))
continue;
State nxt(x, y, cur.key_state, cur.step + 1);
if(grid[x][y] >= 'a' && grid[x][y] <= 'f')
nxt.key_state |= (1 << (grid[x][y] - 'a'));
if(visited[x][y][nxt.key_state]) continue;
visited[x][y][nxt.key_state] = true;
q.push(nxt);
}
}
return -1;
}

private:
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};

bool _check(int key_num, int key_state)
{
return key_state == ((1 << key_num) - 1);
}
};

Share