You find yourself a map of a maze. It looks something like this:
..X..
...*.
.....
.#..#
....T
The initial position is marked with an X. From this position, you can move up, down, left, or right. Your task is to push the secret package, *, into the target destination, T. Blocks marked as # are walls, and neither you nor the secret package can pass through them.
When you move adjacent to the secret package and move towards it, the package is pushed in the same direction. Hence, we can go from
.....
..X*.
.....
.#..#
....T
to
.....
...X*
.....
.#..#
....T
Pushing the package again in the same direction has no effect.
Your task is to find the minimum number of steps you have to take to push the secret package into the target destination.
Input format
A rectangular grid consisting of the characters ., #, X, and T.
Output format
The minimum number of steps required to move the secret package to the target.
Sample input
..X..
...*.
.....
.#..#
....T
Sample output
7