after与迷宫
题号:NC14608
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 128 M,其他语言256 M
64bit IO Format: %lld

题目描述

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

输入描述:

第一行一个正整数T(T<=10),表示共有T组数据。
对于每组数据,第一行四个正整数N,M,r,c(1<=N,M<=1000;1<=r<=N;1<=c<=M)。
接下来N行,每行M个字符,每个表示房间的状态,“.”表示空房间,“*”表示无法进入的房间,“F”表示有墨菲斯托存在的房间,“M”表示有莉莉丝存在的房间。
数据保证(1,1)为“.”。

输出描述:

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

输入

复制
1
4 4 4 3
..**
*F..
*.*.
*M.F

输出

复制
14