Leetcode第864题：获取所有钥匙的最短路径（Shortest path to get all keys）

解题思路

想到最短路径问题，自然想到用BFS解决问题，但是只记录位置还不够，还需要记录当前拥有的钥匙状态。

需要的数据结构

1. 钥匙的个数是\(1-6\)，用一个二进制数表示钥匙的状态，第\(i\)位表示钥匙已经获取到。
2. 队列q记录当前位置以及拥有钥匙的状态，(i,j,state)，\(state\)的第\(i\)位为1表示当前拥有第\(i\)把钥匙。
3. 数组vis记录当前位置是否被访问，\(vis(i,j,state)\)。

步骤

1. 遍历grid，找到起点位置，统计钥匙的个数\(k\)。
2. 从起点出发，加入队列q，并将vis[si][sj][0]置为\(true\)，并判断当前位置是否为终点，即当前位置是否拥有所有的钥匙，即state的二进制表示中的1的个数是否为k。如果是，返回当前的步数（队列出队次数）。
3. 不是终点，从当前位置出发，往四个方向走，如果可以走到下一个位置\((x,y)\)，将\((x,y,next)\)加入队列q。
4. 队列循环结束，没有找到所有的钥匙，退出循环后返回-1。

临界条件

第\(3\)步中的\((x,y)\)需要满足在网格内，如果\((x,y)\)位置是抢，即grid[x][y]=='#'，或者\((x,y)\)的位置是锁，但当前没有对应的钥匙，即grid[x][y] >= 'A' && grid[x][y] <= 'F' && (state >> (grid[x][y] - 'A') & 1) == 0)，则不能走到位置\((x,y)\)。

核心代码如下：

class Solution {
public:
    const static inline vector<int> dirs = {-1, 0, 1, 0, -1};

    int shortestPathAllKeys(vector<string>& grid) {
        int m = grid.size(), n = grid[0].size();
        int k = 0;
        int si = 0, sj = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                char c = grid[i][j];
                // 累加钥匙数量
                if (islower(c)) ++k;
                // 起点
                else if (c == '@') si = i, sj = j;
            }
        }
        queue<tuple<int, int, int>> q{{{si, sj, 0}}};
        vector<vector<vector<bool>>> vis(m, vector<vector<bool>>(n, vector<bool>(1 << k)));
        vis[si][sj][0] = true;
        int ans = 0;
        while (!q.empty()) {
            for (int t = q.size(); t; --t) {
                auto [i, j, state] = q.front();
                q.pop();
                // 找到所有钥匙，返回当前步数
                if (state == (1 << k) - 1) return ans;
                // 往四个方向搜索
                for (int h = 0; h < 4; ++h) {
                    int x = i + dirs[h], y = j + dirs[h + 1];
                    // 在边界范围内
                    if (x >= 0 && x < m && y >= 0 && y < n) {
                        char c = grid[x][y];
                        // 是墙，或者是锁，但此时没有对应的钥匙，无法通过
                        if (c == '#' || (isupper(c) && (state >> (c - 'A') & 1) == 0)) continue;
                        int nxt = state;
                        // 是钥匙，更新状态
                        if (islower(c)) nxt |= 1 << (c - 'a');
                        // 此状态未访问过，入队
                        if (!vis[x][y][nxt]) {
                            vis[x][y][nxt] = true;
                            q.push({x, y, nxt});
                        }
                    }
                }
            }
            // 步数加一
            ++ans;
        }
        return -1;
    }
};

原文地址：http://www.cnblogs.com/hql5/p/16877537.html