Description
Domo is a brilliant dog. By the way, his grandfather is also a brilliant dog, and he has built a giant maze in the forest years ago, which is called "DomoMaze". However Domo is more brilliant, as he made "Bidirectional DomoMaze"!
One day, Domo loses his ball called Wilson in this maze. He wants to take Willson back, and your task is to find out how many ways Domo can reach the position where Willson is.
This "Bidirectional DomoMaze" can be described as a two-dimensional array. With height (H) and width (W), Domo is at the position (0, 0) in the beginning, and Wilson is at the position (A, B)
Each time Domo moves, he can choose one of three ways below:
- from (i, k) to (i+1, k)
- from (i, k) to (i, k+1)
- from (i, k) to (i+1, k+1)
Also, there is a reverse sign block. If Domo step to certain position (i, k) where there is a reverse block, he will change the movement set. The reverse block will dissapear. The movement set as below:
- from (i, k) to (i+1, k)
- from (i, k) to (i, k-1)
- from (i, k) to (i+1, k-1)
If he step the reverse block for the second time, the movement set will reset to the original one.
Input
The first line contains two integers H (2 ≤ H ≤ 15) and W (2 ≤ W ≤ 15) - the height and the width of DomoMaze
The second line contains two integers A (0 ≤ A ≤ H-1) and B (0 ≤ B ≤ W-1) - The Position of the Ball (guaranteed not (0, 0))
For the next H lines, each line has W numbers either 1 or 0 - 0 for empty, and 1 for the reverse block.
Special Testcases:
- Testcase 1-4: A and B will always at (H-1, W-1), no Reverse Block
- Testcase 5-6: A and B can be anywhere, no Reverse Block
- Testcase 7: A and B can be anywhere, one Reverse Block
- Testcase 8: A and B can be anywhere, two Reverse Block
Output
The output only contains a number and a newline character - the number of ways Domo can reach where Wilson is