You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

阿Q被困在了一个 $n \times m$ 的迷宫里，他想知道能否在 t 秒内到达迷宫出口（到达时间小于 t），如果可以，最短时间是多少？

迷宫表示为 $n \times m$ 个格子，格子中字符为'@'的是阿Q目前的位置，字符为'$'的是迷宫的出口，字符为'.' 的表示路，字符为'#'的表示墙，不能通过，字符为'A'到'J'的是门，只有有对应的钥匙才可以通过，对应的钥匙为'a' 到'j'，字符为'a' 到'j'的表示到达这个格子可以得到这把钥匙。迷宫只有一个出口。

输入格式

第一行输入三个整数 $n,m,t（1\leq n,m\leq 20,1 \leq t \leq 100）$，表示迷宫格子的行数和列数。 接下来 n 行，每行 m 个字符表示迷宫的情况。

输出格式

输出一行，包含一个整数，如果阿Q可以在时限内到达，输出最少的时间，否则输出-1。

2 3 5
@A$
.a#

4