1831. 找朋友

时间限制 1000 ms   内存限制 64 MB

找呀 找呀 找朋友
找到一个好朋友
敬个礼 握握手
你是我的好朋友

春天到了,大家都找自己的好朋友出去玩耍,然而大家都不甘示弱,要比比谁最先能找到自己的好朋友。
给出一个 $n\times m$ 的地图,上面有 $k$ 对好朋友,分别用'a','A','b','B', $\ldots$表示。其中大写字母'A'和小写字母'a'是一对好朋友。 小写字母在单位时间内可以向上、向下、向左或向右移动一格(可以穿过障碍物),大写字母不能移动。
请问最快找到好朋友(对应的大写字母)的小写字母是谁?

输入数据

第一行有一个整数 $t\ (1 \le t \le 100)$,表示有 $t$ 组数据。
对于每组数据:
第一行有三个正整数 $n,m,k\ (1\le n,m\le 100,1\le k\le 26)$ ,表示地图的行数、列数和好朋友的对数;
接下来有 $n$ 行,每行有一个长为 $m$ 的字符串,表示地图。'.'表示什么都没有,对应的大写字母和小写字母表示一对好朋友。

输出数据

输出 $t$ 行,每行一个小写字母,表示最快找到好朋友的小写字母。
如果有多个小写字母同时找到好朋友,则输出字典序最小的小写字母。

样例输入

复制
3
2 5 2
aBA..
....b
3 4 3
a..A
b.B.
c.C.
4 4 2
b..A
.B..
....
...a \n
 · · \n
     \n
     \n
 · · \n
    \n
    \n
    \n
 · · \n
    \n
    \n
    \n
    \n

样例输出

复制
a
b
b \n
 \n
 \n

提交

请先 登录

© 2024 FAQs Contact About