Problem Description
Darth Tater, known before as Jiahai the Potato, has been forming a plan to attack the Rainbow Catlands, where happy cats and rainbows live in harmony. After turning towards the dark side, Darth Tater has broken off all connections to his previous master, the wise master Rar. However, while planning his grand master scheme to eliminate Master Rar once and for all, he has encountered a serious problem. His imperial star destroyers have been unable to traverse the densely populated asteroid field seperating them and Rainbow Catlands. The hardworking and dead imperial engineers have been working to attach booster engines to the asteroids to move them out of the star destroyer's way.
The asteroids and star destroyers are located on a plane (the 2D one not the flying one), and have a width of 1, a length larger than 1, and a direction (vertical or horizontal). Due to the lack of imperial engineers (the good ones had been baked by Darth Tater), the booster engine on the asteroids and star destroyer can only propel the objects along a certain direction parallel to its length. For example, in the asteroid field below, the asteroid #1 in Fig. 1 can only move up or down. The star destroyer is represented by "X" and can be of any valid length.
Input
The first line of input will consist of two integers, the number of rows M and the number of columns N in the asteroid field.
The next line of input will consist of two integers, the goal row A and the goal column B The goal row and goal column do not include the border '@'s and start from 0.
The next M + 2 lines will consist of N + 2 characters, representing the asteroid field. The asteroid field is guaranteed to be surrounded by '@'s. Every distinct asteroid will be represented by a unique alphanumeric character.
Output
A single integer, the least amount of moves required to move the star destroyer to reach the goal row and goal column. There will always be a way for Darth Tater to succeed.
Limits
Subtask 1 (3 points): M ≤ 2
Subtask 2 (7 points): M ≤ 3
Subtask 3 (90 points): M ≤ 7, N ≤ 7
Sample Testcase 1
Input
6 6
2 5
@@@@@@@@
@[email protected]
@[email protected]
@[email protected]
@[email protected]
@[email protected]
@[email protected]
@@@@@@@@
Output
3
Explanation
It is possible to move the star destroyer to the desired row and column in 3 moves.
Firstly, move asteroid #2 leftwards. After moving asteroid #1 downwards, the star destroyer can reach row 2 and column 5 in the next move