Save the Princess!!!

3.7

3 votes
Problem

This is about a Prince who wants to rescue her Princess from a bunch of ferocious monsters. You are given a grid of size n+2 and m. Prince initially knows the initial positioning of the monsters on the grid. It is night time so the Prince has an upper hand over the monsters(as the monsters can't see anything at night).

Prince is initially at the top left corner and the Princess is held by the monsters at the bottom right corner. But wait wait wait reaching the other end is not that easy. Prince needs to pass through a forest of size n * m. You need to get to the other end of the grid but your moves needs to be subtle, you don't want the monsters to know when you pass by(i.e. the position of the monster and Prince can't be same simultaneously).

After every move monster moves to the next position, but take care of the fact that the direction in which monster moves alternates between the rows. Monsters in the first row of the forest moves in left direction, and that of next row in right direction. Once the monster reaches the boundary of the forest it'll teleport to the other end of that row. Prince is allowed to move to any of the adjacent position or it can stay at the same place considering there is no monster at that position as he makes the move.

Help Prince to rescue her Princess from those ferocious monsters.

Note : No monster will be there in the first and last row. Prince can move freely in the first and the last row as there are no monsters there.

Input : There will be two integers n and m, number of rows and columns respectively. The next n+2 lines consists of m characters, this is the initial positioning of the monsters that the Prince knows. The character X indicates a Monster, '.' indicates an empty cell, B indicates the beginning position and T indicates the target position.

Constrains : 1<=n<=50 1<=m<=50

Output : Print the minimum number of moves required to reach the target point. If it is not possible to reach the other end print "Impossible".

Time Limit: 5
Memory Limit: 256
Source Limit:
Editor Image

?