1. 问题背景与核心挑战LeetCode 864题获取所有钥匙的最短路径是一个典型的图论与状态压缩结合的算法问题。给定一个二维网格其中包含起点 墙壁 #空地 .小写字母表示钥匙a-f大写字母表示对应的锁A-F玩家需要收集所有钥匙每个字母钥匙只能开对应字母的锁求从起点出发收集全部钥匙的最短路径步数。这个问题在现实中有诸多应用场景比如游戏中的关卡设计如解谜游戏中的钥匙门机制物流仓储中的权限区域访问网络安全中的多级认证路径优化关键难点在于路径搜索过程中需要动态记录已获取的钥匙状态传统的BFS无法直接处理这种带有状态变化的路径搜索。2. 算法选择与思路解析2.1 为什么选择BFS状态压缩常规BFS适用于无权图的最短路径查找但本题的特别之处在于路径有效性取决于钥匙获取状态同一位置在不同钥匙状态下应被视为不同节点状态压缩使用位运算来表示钥匙获取情况Java中int类型足够表示a-f六把钥匙每位代表一把钥匙a10, b11,...按位或操作记录新钥匙按位与操作检查是否有对应钥匙2.2 三维状态表示法我们需要扩展传统的(x,y)坐标到(x,y,keys)三维状态keys的二进制表示当前持有的钥匙例如keys0b000101表示持有a和c钥匙目标状态是持有所有钥匙对于k把钥匙是(1k)-13. Java实现详解3.1 数据结构设计class State { int x, y; int keys; State(int x, int y, int keys) { this.x x; this.y y; this.keys keys; } // 重写equals和hashCode用于HashSet Override public boolean equals(Object o) {...} Override public int hashCode() {...} }3.2 BFS核心框架public int shortestPathAllKeys(String[] grid) { int m grid.length, n grid[0].length(); int allKeys 0; QueueState queue new LinkedList(); SetState visited new HashSet(); // 初始化找到起点和所有钥匙 for (int i 0; i m; i) { for (int j 0; j n; j) { char c grid[i].charAt(j); if (c ) { queue.offer(new State(i, j, 0)); visited.add(new State(i, j, 0)); } else if (c a c f) { allKeys | (1 (c - a)); } } } int[][] dirs {{0,1},{1,0},{0,-1},{-1,0}}; int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { State curr queue.poll(); if (curr.keys allKeys) return steps; for (int[] dir : dirs) { int x curr.x dir[0]; int y curr.y dir[1]; int keys curr.keys; if (x 0 || x m || y 0 || y n) continue; char c grid[x].charAt(y); if (c #) continue; // 墙 // 遇到锁且没有对应钥匙 if (c A c F (keys (1 (c - A))) 0) continue; // 遇到钥匙则更新状态 if (c a c f) keys | (1 (c - a)); State newState new State(x, y, keys); if (!visited.contains(newState)) { visited.add(newState); queue.offer(newState); } } } steps; } return -1; }4. 关键优化与注意事项4.1 状态判重优化常规BFS使用二维坐标判重但本题需要三维判重x,y,keys。实测发现使用HashSet 存储已访问状态必须正确实现State类的equals和hashCode方法错误示例仅比较x,y会导致错误剪枝4.2 方向数组技巧使用dirs数组表示四个方向比写四个if更简洁int[][] dirs {{0,1},{1,0},{0,-1},{-1,0}}; // 右,下,左,上4.3 钥匙数量计算可以在初始化时统计钥匙数量int keyCount 0; for (String row : grid) { for (char c : row.toCharArray()) { if (c a c f) keyCount; } } allKeys (1 keyCount) - 1;5. 复杂度分析与边界情况5.1 时间复杂度设网格大小为M×N钥匙数量为K状态总数M×N×2^K每个状态处理O(1)四个方向总复杂度O(M×N×2^K)5.2 空间复杂度主要消耗在visited集合O(M×N×2^K)5.3 特殊测试用例无钥匙情况应返回0钥匙被墙包围返回-1需要绕路获取钥匙顺序的情况最大网格尺寸30x30和最多钥匙6把的性能测试6. 实际应用扩展这种BFS状态压缩的技术还可用于多目标点最短路径问题如同时收集多个物品动态障碍物场景如随时间变化的迷宫多条件解锁的路径规划如需要特定道具组合在游戏AI中类似的算法可用于NPC的寻路决策自动解谜系统关卡难度测试7. 常见错误与调试技巧7.1 典型错误模式忘记处理锁的检查条件// 错误漏掉钥匙检查 if (c A c F) continue;钥匙状态更新错误// 错误直接修改curr.keys会影响其他方向 curr.keys | (1 (c - a));状态判重不完整// 错误仅用坐标判重 visited.add(x , y);7.2 调试建议打印关键状态System.out.println(x,y keys:Integer.toBinaryString(keys));可视化小规模测试用例a.A ... B.b使用单元测试覆盖无钥匙情况不可达情况需要特定顺序的情况8. 算法变种与进阶8.1 多玩家协作版本假设可以有多人同时移动求最短时间。这需要状态扩展为(x1,y1,x2,y2,keys)协同移动策略8.2 带权版本如果不同格子有不同的移动代价如沼泽减速可以改用Dijkstra算法。8.3 动态障碍物如果障碍物会随时间变化状态需要增加时间维度。9. 性能优化实战当网格较大30x30且钥匙较多6把时使用位运算优化状态处理双向BFS搜索启发式搜索A*// 估算剩余步数曼哈顿距离到最远钥匙 PriorityQueueState pq new PriorityQueue(Comparator.comparingInt(s - s.steps heuristic(s)));10. 工程实践建议将网格解析与BFS逻辑分离使用常量定义方向数组添加详细的注释说明状态表示编写完备的单元测试对于游戏开发实际应用可以考虑预处理可通行区域分层路径规划结合导航网格(NavMesh)技术 
长河君 · 2026/9/11 11:47:00 · 阅读 1.2k LeetCode 864：BFS与状态压缩解决钥匙收集最短路径问题
1. 问题背景与核心挑战LeetCode 864题获取所有钥匙的最短路径是一个典型的图论与状态压缩结合的算法问题。给定一个二维网格其中包含起点 墙壁 #空地 .小写字母表示钥匙a-f大写字母表示对应的锁A-F玩家需要收集所有钥匙每个字母钥匙只能开对应字母的锁求从起点出发收集全部钥匙的最短路径步数。这个问题在现实中有诸多应用场景比如游戏中的关卡设计如解谜游戏中的钥匙门机制物流仓储中的权限区域访问网络安全中的多级认证路径优化关键难点在于路径搜索过程中需要动态记录已获取的钥匙状态传统的BFS无法直接处理这种带有状态变化的路径搜索。2. 算法选择与思路解析2.1 为什么选择BFS状态压缩常规BFS适用于无权图的最短路径查找但本题的特别之处在于路径有效性取决于钥匙获取状态同一位置在不同钥匙状态下应被视为不同节点状态压缩使用位运算来表示钥匙获取情况Java中int类型足够表示a-f六把钥匙每位代表一把钥匙a10, b11,...按位或操作记录新钥匙按位与操作检查是否有对应钥匙2.2 三维状态表示法我们需要扩展传统的(x,y)坐标到(x,y,keys)三维状态keys的二进制表示当前持有的钥匙例如keys0b000101表示持有a和c钥匙目标状态是持有所有钥匙对于k把钥匙是(1k)-13. Java实现详解3.1 数据结构设计class State { int x, y; int keys; State(int x, int y, int keys) { this.x x; this.y y; this.keys keys; } // 重写equals和hashCode用于HashSet Override public boolean equals(Object o) {...} Override public int hashCode() {...} }3.2 BFS核心框架public int shortestPathAllKeys(String[] grid) { int m grid.length, n grid[0].length(); int allKeys 0; QueueState queue new LinkedList(); SetState visited new HashSet(); // 初始化找到起点和所有钥匙 for (int i 0; i m; i) { for (int j 0; j n; j) { char c grid[i].charAt(j); if (c ) { queue.offer(new State(i, j, 0)); visited.add(new State(i, j, 0)); } else if (c a c f) { allKeys | (1 (c - a)); } } } int[][] dirs {{0,1},{1,0},{0,-1},{-1,0}}; int steps 0; while (!queue.isEmpty()) { int size queue.size(); for (int i 0; i size; i) { State curr queue.poll(); if (curr.keys allKeys) return steps; for (int[] dir : dirs) { int x curr.x dir[0]; int y curr.y dir[1]; int keys curr.keys; if (x 0 || x m || y 0 || y n) continue; char c grid[x].charAt(y); if (c #) continue; // 墙 // 遇到锁且没有对应钥匙 if (c A c F (keys (1 (c - A))) 0) continue; // 遇到钥匙则更新状态 if (c a c f) keys | (1 (c - a)); State newState new State(x, y, keys); if (!visited.contains(newState)) { visited.add(newState); queue.offer(newState); } } } steps; } return -1; }4. 关键优化与注意事项4.1 状态判重优化常规BFS使用二维坐标判重但本题需要三维判重x,y,keys。实测发现使用HashSet 存储已访问状态必须正确实现State类的equals和hashCode方法错误示例仅比较x,y会导致错误剪枝4.2 方向数组技巧使用dirs数组表示四个方向比写四个if更简洁int[][] dirs {{0,1},{1,0},{0,-1},{-1,0}}; // 右,下,左,上4.3 钥匙数量计算可以在初始化时统计钥匙数量int keyCount 0; for (String row : grid) { for (char c : row.toCharArray()) { if (c a c f) keyCount; } } allKeys (1 keyCount) - 1;5. 复杂度分析与边界情况5.1 时间复杂度设网格大小为M×N钥匙数量为K状态总数M×N×2^K每个状态处理O(1)四个方向总复杂度O(M×N×2^K)5.2 空间复杂度主要消耗在visited集合O(M×N×2^K)5.3 特殊测试用例无钥匙情况应返回0钥匙被墙包围返回-1需要绕路获取钥匙顺序的情况最大网格尺寸30x30和最多钥匙6把的性能测试6. 实际应用扩展这种BFS状态压缩的技术还可用于多目标点最短路径问题如同时收集多个物品动态障碍物场景如随时间变化的迷宫多条件解锁的路径规划如需要特定道具组合在游戏AI中类似的算法可用于NPC的寻路决策自动解谜系统关卡难度测试7. 常见错误与调试技巧7.1 典型错误模式忘记处理锁的检查条件// 错误漏掉钥匙检查 if (c A c F) continue;钥匙状态更新错误// 错误直接修改curr.keys会影响其他方向 curr.keys | (1 (c - a));状态判重不完整// 错误仅用坐标判重 visited.add(x , y);7.2 调试建议打印关键状态System.out.println(x,y keys:Integer.toBinaryString(keys));可视化小规模测试用例a.A ... B.b使用单元测试覆盖无钥匙情况不可达情况需要特定顺序的情况8. 算法变种与进阶8.1 多玩家协作版本假设可以有多人同时移动求最短时间。这需要状态扩展为(x1,y1,x2,y2,keys)协同移动策略8.2 带权版本如果不同格子有不同的移动代价如沼泽减速可以改用Dijkstra算法。8.3 动态障碍物如果障碍物会随时间变化状态需要增加时间维度。9. 性能优化实战当网格较大30x30且钥匙较多6把时使用位运算优化状态处理双向BFS搜索启发式搜索A*// 估算剩余步数曼哈顿距离到最远钥匙 PriorityQueueState pq new PriorityQueue(Comparator.comparingInt(s - s.steps heuristic(s)));10. 工程实践建议将网格解析与BFS逻辑分离使用常量定义方向数组添加详细的注释说明状态表示编写完备的单元测试对于游戏开发实际应用可以考虑预处理可通行区域分层路径规划结合导航网格(NavMesh)技术