### 问题描述 小蓝在地下城中探险。地下城是个多层结构，小蓝从大门所在格子进入当前这一层，如果想要去往下一层，则需要集齐所有的钥匙回到大门处打开去往下一层的大门。 已知小蓝当前所在的层是一个大小为 $m \times n$ 的迷宫，该迷宫内存在着 $k$ 把钥匙。小蓝每一步可以移动一格，但是无法穿过墙壁。 请你求出小蓝集齐所有钥匙打开大门的最少步数。 ### 输入格式 输入数据有 $m+1$ 行。 第一行为三个整数 $m,n,k$ ，表示迷宫大小为 $m \times n$ ，其中钥匙数量为 $k$ 。 接下来 $m$ 行，每行有 $n$ 个字符，其中 $@$ 符号表示大门，$!$ 符号表示钥匙，$\#$ 符号表示墙壁，$*$ 符号表示可以行走的地面。 保证除第一行外的输入数据只有以上四种字符，且 $@$ 只有一个， $!$ 有 $k$ 个。 ### 输出格式 输出一个整数，表示最少步数。如果无法打开大门，则输出 $-1$ 。 ### 样例输入1 ```text 2 3 2 @#! **! ``` ### 样例输出1 ```text 8 ``` ### 样例输入2 ```text 2 2 1 @# #! ``` ### 样例输出2 ```text -1 ``` ### 评测数据规模 对于所有评测数据， $1\leq m,n \leq 30$ ， $0\leq k \leq 6$ 。