224. Rat in a Maze
MediumBacktrackingDFS
In an n×n maze (1 = open, 0 = blocked) find all paths from the top-left to the bottom-right moving U, D, L, R without revisiting a cell. Print the paths as direction strings in lexicographic order, space-separated, or -1 if none.
Input format
Line 1: n Next n lines: n values
Output format
The paths, or -1.
Example 1
Input
4 1 0 0 0 1 1 0 1 1 1 0 0 0 1 1 1
Output
DDRDRR DRDDRR
Example 2
Input
2 1 0 1 0
Output
-1
Constraints
2 ≤ n ≤ 5
Read input from standard input and print the answer to standard output. Your code is judged against 3 test cases, most of them hidden.
Loading the MyLoginn IDE…