Problem 21255 --C:迷宫逃出

21255: C:迷宫逃出

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 6  Solved: 2
[Submit][Status][Web Board][Creator:][下载FPS1元][添加到购物车][下载测试数据1元][20kb]

Description

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

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

Input

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

Output


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

Sample Input

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

Sample Output

6
-1

HINT

Source

[Submit][Status]