User's AC Ratio

61.5% (16/26)

Submission's AC Ratio

27.6% (27/98)

Description

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.

Input Format

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.

Output Format

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.

Sample Input 1

5
r w r r r
r r r w r
w w w r r
r r w r w
w r r r r

Sample Output 1

0 0
0 1
1 1
2 1
2 0
3 0
4 0
4 1
4 2
3 2
3 3
3 4
4 4

Hints

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.

Problem Source

Subtasks

No. Testdata Range Score
1 0~4 15

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 1000 65536 65536 1
1 1000 65536 65536 1
2 1000 65536 65536 1
3 1000 65536 65536 1
4 1000 65536 65536 1