10685: C：迷宫逃出

我的名字是工藤新一
是解决困难案件的高中生名侦探
可是有一天被神秘的组织灌下了毒药
身体缩小了
变成了江户川柯南
身体虽然变小
头脑还是一样
不管什么案件
真相永远只有一个
——江户川柯南

为了躲避黑暗组织的追踪，柯南不慎逃入一个远古的迷宫，机智的柯南马上通过卫星电话手表从阿笠博士那获取了迷宫地图。不幸的是，迷宫的出口有3个钥匙插槽，必须同时集齐这3把不同的钥匙才能打开出口的门。而这3把钥匙分别分布在迷宫中不同的地方。
假设只有移动需要时间，柯南只能上下左右移动，并且每秒只能移动一格，迷宫中的墙壁无法穿越。柯南再不逃离，黑暗组织就要追进来了。他能逃离吗？如果能，最快需要多少秒才能打开出口逃离迷宫呢？

输入数据的第一行是一个整数T，表示有T组测试样例，接着是T块数据，每块数据先是两个整数n和m，分别表示迷宫的行数和列数，接着是个n行m列的字符矩阵表示迷宫地图，一个字符代表迷宫一格，’S’表示柯南当前所在地，’D’表示出口，’.’表示普通的路，’*’表示墙壁，’A’、’B’、’C’分别表示3把不同的钥匙。T<=10，2<n,m<=20。

对于每组测试样例，如果柯南可以逃离，输出柯南逃离迷宫所需最短时间并独占一行；如果柯南无法逃离，输出-1并独占一行。

2
3 3
D.C
*..
SAB
4 3
D*A
..*
S.B
.C.

6
-1