Home Web Board ProblemSet Standing Status Statistics
long long输出请使用 %lld服务器的python版本为3.4
Problem I: after与迷宫

Problem I: after与迷宫

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 66  Solved: 12
[Submit][Status][Web Board]

Description

after的算法书的遗落在一个叫做AIJ的迷宫中了,这个迷宫有N*M个房间,迷宫的入口为(11),算法书遗落在(rc)。迷宫中的房间有四种状态:空房间、无法进入的房间、有墨菲斯托存在的房间和有莉莉丝存在的房间。墨菲斯托会否定一切,而莉莉丝会诱惑人做一种叫做YK的活动。after是一个意志薄弱的人,他遇到了墨菲斯托和莉莉丝之后,便会变成眼神空洞的超级YK机器人。after每步可以从他当前的房间走至上下左右四个房间的其中一个房间。after害怕变成超级YK机器人,所以要尽快拿到算法书然后从入口逃离。问after最少需要走多少步才可以在不变成超级YK机器人的情况下从入口出发取回算法书并逃离迷宫?

Input

第一行一个正整数T(T<=10),表示共有T组数据。

对于每组数据,第一行四个正整数NMrc(1<=N,M<=10001<=r<=N1<=c<=M)

接下来N行,每行M个字符,每个表示房间的状态,“.”表示空房间,“*”表示无法进入的房间,“F”表示有墨菲斯托存在的房间,“M”表示有莉莉丝存在的房间。

数据保证(11)(rc)均为“.”。

Output

对每组数据输出一行,即after最少需要走的步数。若after无法取回算法书,则输出“IMPOSSIBLE(不带引号)

Sample Input

1
4 4 4 3
..**
*F..
*.*.
*M.F

Sample Output

14

HINT

after只遇到墨菲斯托或者只遇到莉莉丝是不会变成超级YK机器人的,只有两者都遇到的情况下才会变成超级YK机器人。

[Submit][Status][Web Board]