问题 B: 大神的探险 之 寻找宝藏

时间限制: 1Sec 内存限制: 128MB 提交: 0 解决: 0

题目描述
cqy终于算出了坑爹的密码!!!进入墓穴,发现墓穴是一个n*m的矩阵。由于墓穴极度缺氧,cqy必须用最短的时间找到唯一的宝藏。墓穴里险象环生,除了有各种各样的陷阱,还有野怪出没!!!cqy每前进一步需要1分钟的时间,如果遇到野怪,还要多花费1分钟来打倒野怪。当然cqy不会往陷阱走,那就有去无回了...如果cqy、宝藏、陷阱、野怪的位置全部已知,那么cqy最短要用多长时间找到宝藏?

输入
有多组测试数据。对于每组测试数据,首先有两个整数n和m(1<n,m<50),接下来有n行,每行有m个字符,A表示宝藏,C表示cqy,E表示正常的道路,X表示陷阱,T表示野怪。

输出

对于每组测试数据,在一行内输出找到宝藏所需的最短时间,如果无法找到宝藏,则输出“Game Over!”

样例输入
4 4
ATTE
EXTE
ETCE
EXEX
2 3
CXE
TXA
样例输出
5
Game Over!
提示

比赛公告

 大连交通大学 2015年春大连市选拔赛  大家加油!