题目描述

给定一个大小为 $m\times n$ 二维网格 $grid$ ，其中：

• . 代表一个空房间
• # 代表一堵墙
• @ 是起点
• 小写字母代表钥匙
• 大写字母代表锁

我们从起点开始出发，一次移动是指向四个基本方向（上下左右）之一行走一个单位空间。我们不能在网格外面行走，也无法穿过一堵墙。如果途经一个钥匙，我们就把它捡起来。除非我们手里有对应的钥匙，否则无法通过锁。

假设 $k$ 为 钥匙/锁 的个数，且满足 $1 <= k <= 6$，字母表中的前 $k$ 个字母在网格中都有自己对应的一个小写和一个大写字母。换言之，每个锁有唯一对应的钥匙，每个钥匙也有唯一对应的锁。另外，代表钥匙和锁的字母互为大小写并按字母顺序排列。

输出获取所有钥匙所需要的移动的最少次数。如果无法获取所有钥匙，输出 $-1$ 。

输入格式

第一行两个空格隔开的整数 $m$ 和 $n$, 表示行和列。

接下来的 $m$ 行，每行一个长度为 $n$ 的字符串。

输出格式

一行一个整数表示答案。

样例 1：

3 5
@.a..
###.#
b.A.B

8

解释： 目标是获得所有钥匙，而不是打开所有锁。

样例 2：

3 5
@..aA
..B#.
....b

6

样例 3:

1 3
@Aa

-1

提示：

对于 其中 $20\%$ 的数据，$grid[i][j]$ 只含有 ., @, a；

对于 其中另 $10\%$ 的数据，$grid[i][j]$ 只含有 ., @, a～f；

对于 其中另 $10\%$ 的数据，$grid[i][j]$ 只含有 ., @, a～f以及 A～F；

对于 $100\%$ 的数据：

• $1 <= m, n <= 30$
• $grid[i][j]$ 只含有 ., #, @, a～f 以及 A～F
• 钥匙的数目范围是 $[1, 6]$
• 每个钥匙都对应一个 不同 的字母
• 每个钥匙正好打开一个对应的锁

source

864. 获取所有钥匙的最短路径