#K71452. All Paths in a Matrix
All Paths in a Matrix
All Paths in a Matrix
You are given an m x n matrix of integers. Your task is to find all possible paths from the top-left corner to the bottom-right corner of the matrix, where you can only move right (R) or down (D). Each path should be represented as a string consisting of the characters 'R' and 'D'.
Note: In the case of a single cell matrix (1x1), the only valid path is an empty string. For matrices with only one row or one column, there will be only one possible path.
Example:
Matrix: 1 2 3 4 5 6 7 8 9</p>Possible paths (in sorted order): DDRR DRDR DRRD RDDR RDRD RRDD
Your solution must read the input from stdin and output the results to stdout.
inputFormat
The first line of input contains two integers m and n, denoting the number of rows and columns of the matrix respectively. The following m lines each contain n space-separated integers representing the matrix.
Example:
3 3 1 2 3 4 5 6 7 8 9
outputFormat
Print all valid paths from the top-left corner to the bottom-right corner, one per line, in lexicographical order. Each path is a string consisting solely of the characters 'R' and 'D'.
Example:
DDRR DRDR DRRD RDDR RDRD RRDD## sample
3 3
1 2 3
4 5 6
7 8 9
DDRR
DRDR
DRRD
RDDR
RDRD
RRDD