URI Online Judge | 2081

Dreams, Believe Them!

By XII Maratona de Programação IME-USP, 2008 BR Brazil

Timelimit: 1

One of the most important political activists of the world was Dr. Martin Luther King Jr., whose most famous speech was "I have a dream". In 1964, he received the Nobel Peace Prize for his commitment to the struggle to end racial prejudice in the United States, and for his leadership in nonviolent movements. Shortly after receiving the award, King was assassinated moments before a march in Memphis.

In addition to the commitment to political struggle, Luther King enjoyed playing puzzles. One of the games he loved to play is as follows: two maps N-by-M, each with a robot provided. Each map contains a start and an end point. Some "tiles" of the map are surrounded by walls. A tile of the map may or may not be a hole. A command given (Up, Down, Left, Right) runs simultaneously to both maps. Robots do not go through the walls and even float over the holes. The goal is to get the two robots at the end point at the same time, using up to 50 movements, if possible.

In this problem, your task is given two maps N-by-M, determine the minimum number of moves that solves the problem.


The input is composed of several instances. The first line of input contains an integer T indicating the number of instances.

The first line of the instance has two integers N and M (1 ≤ N, M ≤ 50), indicating the number of lines of the maps and the number of columns of the maps, respectively. In the following lines are given the two maps. For each map we will have N rows with M characters. The character "." indicates a free position; "#" Indicates a position surrounded by walls; "B" indicates a hole; "R" indicates the starting position of the robot and "F" indicates the final position of the robot.


For each instance print a line containing the minimum number of moves that solves the problem, or "impossivel" if you can not solve the problem with a maximum of 50 moves.

Sample Input Sample Output

4 4
4 4