TAs are now developing a brand new version of robot that can run through a given maze as fast as possible, but we are facing a serious problem about finding the path from begin to end. Since you are so clever, please help us to solve this problem.
Notice that only vertical and horizontal steps are valid.
First line of input is a number $n \ (n \leq 25)$, which represents the size of maze.
Following is an $n \times n$ matrix which is the maze itself, with $w$ and $r$ represent walls and road respectively.
Couple lines to show the path from begin$(0, 0)$/upper-left to the end$(n-1, n-1)$/bottom-right.
Each line should have format $x \ y$, with $x$ represents horizontal axis and $y$ represents vertical one.
Notice that there is only a single path from begin to end, so you do not need to concern about cases of more than one path.
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0~4 | 15 |
| No. | Time Limit (ms) | Memory Limit (KiB) | Output Limit (KiB) | Subtasks |
|---|---|---|---|---|
| 0 | 1000 | 65536 | 65536 | |
| 1 | 1000 | 65536 | 65536 | |
| 2 | 1000 | 65536 | 65536 | |
| 3 | 1000 | 65536 | 65536 | |
| 4 | 1000 | 65536 | 65536 |