算法搜索

带压缩的额外状态的 BFS

字数统计: 994字   |   阅读时长: 4分
,

摘要: 带压缩的额外状态的 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