0864. Shortest Path to Get All Keys ======================================================================================================================== 题目信息 -------- :题号: 0864 :难度: Hard :主题: 网格、钥匙与锁、最短路径 :原题: `LeetCode 0864 `_ :重点: 移动状态包含当前位置和已持有钥匙集合;钥匙取得后永久保留,对应大写锁只有持有同字母钥匙时才能进入 题目重述 -------- 给定字符网格 ``grid``。字符 ``@`` 是唯一的起点,``.`` 是空地,``#`` 是不可进入的墙,小写字母表示钥匙,大写字母表示对应的锁。 每一步可以向上、下、左、右移动一格,不能越界或穿过墙。进入钥匙格后会永久获得该钥匙;只有已经持有对应小写钥匙时,才能进入相应的大写锁格。目标只是收集全部钥匙,不要求打开全部锁。请返回最少移动步数;若无法收集齐,返回 ``-1``。 ``m == grid.length``,``n == grid[i].length``,``1 <= m, n <= 30``。网格恰有一个起点,并存在 ``k`` 把钥匙,其中 ``1 <= k <= 6``;使用的钥匙依次为字母 ``a`` 至第 ``k`` 个小写字母,每把钥匙和对应的大写锁都恰好出现一次。 自建示例 -------- 取得钥匙后穿过对应锁寻找下一把钥匙: .. code-block:: text 输入:grid = ["@.aA","###.","B..b"] 输出:5 解释:从起点向右两步取得 a,再向右穿过锁 A,向下两步到达 b,共移动 5 步并收集全部钥匙。锁 B 与钥匙 b 都存在,但目标完成后不必再打开 B。 一把钥匙被另一把钥匙的锁阻挡: .. code-block:: text 输入:grid = ["@Bb","aA#"] 输出:-1 解释:可以先向下取得 a 并穿过锁 A,但通道在墙处结束;钥匙 b 位于锁 B 后方,而通过 B 又必须先取得 b,因此无法收集全部钥匙。