前言
重复刷太多相同的题目很容易产生思维惯性。像习惯了套公式，就忘了判断是否满足使用条件或者不会对公式进行变形。导致题目一点点的改变，就让人产生似是而非的错觉，但其实本质还是一样，只是自己没有培养发现本质的能力。没有总结和思考的刷题，反而会成为限制我们发挥的负担。孔子说过：学而不思则罔。
题目: 864. 获取所有钥匙的最短路径
与空间中的三维不同，我们做题中的三维通常是于状态有关。第三维通常是表示这些状态的集合。想本题中的第三位就是表示收集到的钥匙的状态。本题最多6把钥匙，所以共有2^6 + 1 = 65个状态（如没有钥匙、只有第一把钥匙，有第一把和第三把钥匙等等）。只要我们遍历完地图中每个位置的每个状态，我们必能得到最终结果。因为是求最短路径，所以我们套用广度搜索。
关键点：
1，用三维数组记录遍历状态，但收集的钥匙状态不同地图中的相同位置可以重复进入，所以要用三维。
2，表示钥匙的状态，如果直接用数组表示每把钥匙的状态，不仅要记录的维度增加了，而且判断的复杂度也提高了。所以可以用位运算表示钥匙的状态，用一个整数的6位，每一位表示一把钥匙。当6位全为1时，表示收集完成。
3，注意特殊条件。如只有收集了钥匙之后，第三维才会改变。遇到门的处理。
代码：
三维数组
class Solution {vector<vector<int>> idxs; // 表示方向vector<vector<vector<int>>> flag; // 记录访问过的三维坐标public:Solution() : idxs({{1, 0}, {-1, 0}, {0, 1}, {0, -1}}), flag(31, vector<vector<int>>(31, vector<int>(65, 0))) {} // 初始化int shortestPathAllKeys(vector<string>& grid) {int n = grid.size(), m = grid[0].size();queue<vector<int>> que;int cnt = 0;for(int i = 0; i < grid.size(); ++ i){ // 记录起点和钥匙的数量for(int j = 0; j < grid[0].size(); ++ j){if(grid[i][j] == '@'){que.push({i, j, 0});grid[i][j] = '.';flag[i][j][0] = 1;}else if(grid[i][j] >= 'a' && grid[i][j] <= 'f') cnt ++;}}int step = 0, ultimately = (1 << cnt) - 1; // 表示步数和集齐钥匙的状态while(!que.empty()){int sz = que.size();for(int i = 0; i < sz; i ++){auto D = que.front();if(D[2] == ultimately) return step; // 结束条件que.pop();for(int j = 0; j < 4; j ++){int idx1 = D[0] + idxs[j][0], idx2 = D[1] + idxs[j][1];if(idx1 * idx2 < 0 || idx1 >= grid.size() || idx2 >= grid[0].size() || grid[idx1][idx2] == '#') // 边界条件，越界和撞墙continue;// 特殊条件，已经遍历过和没有钥匙开门if(flag[idx1][idx2][D[2]]) continue;char c = grid[idx1][idx2];if(c > '@' && c < 'G' && (D[2] & (1 << c - 'A')) == 0) continue;int state = D[2]; // 记得更新第三维度if(c >= 'a' && c <= 'f') state |= 1 << c - 'a';que.push({idx1, idx2, state});flag[idx1][idx2][state] = 1;}}step ++;}return -1;}
};
进一步压缩状态，用31-16位表示第一维， 15-8表示第二位，7-0表示第三维。把坐标压缩为一个整数，并用字典标记位置
class Solution {vector<vector<int>> idxs; // 表示方向unordered_set<int> visited; // 记录访问过的三维坐标public:Solution() : idxs({{1, 0}, {-1, 0}, {0, 1}, {0, -1}}){} // 初始化int toBinary(int x, int y, int z){return (x << 16) + (y << 8) + z;}vector<int> fromBinary(int value) {vector<int> coor(3);coor[2] = value & 0xFF; // 提取最后8位coor[1] = (value >> 8) & 0xFF; // 右移8位，然后提取最后8位coor[0] = (value >> 16) & 0xFF; // 右移16位，然后提取最后8位return coor;}int shortestPathAllKeys(vector<string>& grid) {int n = grid.size(), m = grid[0].size();queue<int> que;int cnt = 0;for(int i = 0; i < grid.size(); ++ i){ // 记录起点和钥匙的数量for(int j = 0; j < grid[0].size(); ++ j){if(grid[i][j] == '@'){int state = toBinary(i, j, 0);que.push(state);grid[i][j] = '.';visited.insert(state);}else if(grid[i][j] >= 'a' && grid[i][j] <= 'f') cnt ++;}}int step = 0, ultimately = (1 << cnt) - 1; // 表示步数和集齐钥匙的状态while(!que.empty()){int sz = que.size();for(int i = 0; i < sz; i ++){auto x = que.front();auto D = fromBinary(x);if(D[2] == ultimately) return step; // 结束条件que.pop();for(int j = 0; j < 4; j ++){int idx1 = D[0] + idxs[j][0], idx2 = D[1] + idxs[j][1];if(idx1 * idx2 < 0 || idx1 >= grid.size() || idx2 >= grid[0].size() || grid[idx1][idx2] == '#') // 边界条件，越界和撞墙continue;// 特殊条件，已经遍历过和没有钥匙开门char c = grid[idx1][idx2];if(c > '@' && c < 'G' && (D[2] & (1 << (c - 'A'))) == 0) continue;int state = D[2]; // 记得更新第三维度if(c >= 'a' && c <= 'f') state |= 1 << (c - 'a');state = toBinary(idx1, idx2, state);if(visited.count(state)) continue;que.push(state);visited.insert(state);}}step ++;}return -1;}
};
反思
当时一直想用二位坐标加步数表示状态，所以一直思考不出来。原因时在写二维题目时，习惯性只考虑坐标和目标这两个元素。所以要多分析题目中的新元素，对比与经验中的不同点。