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