← 返回 oracle 的题目列表Enumerate All Valid Grid Paths
类型：online_judge
Given an m x n binary matrix grid:
1 represents a passable cell;
0 represents a blocked cell.
Find all valid paths from the top-left cell (0, 0) to the bottom-right cell (m - 1, n - 1). You may move only Right (R) or Down (D).
Represent each path as a string of R and D. Output paths in lexicographic order. Since D < R, DFS should try Down before Right. If no path exists, output NO PATH.
Input
m n
grid[0][0] grid[0][1] ... grid[0][n-1]
...
grid[m-1][0] ... grid[m-1][n-1]
Output
one path per line; output NO PATH if none exists
Constraints
1 <= m, n <= 10
Since all paths are returned, the number of results can be exponential.
Example
Input:
3 3
1 1 1
1 0 1
1 1 1
Output:
DDRR
RRDD
Example
Input
3 3
1 1 1
1 0 1
1 1 1
Output
DDRR
RRDD