Enumerate Right-and-Down Paths Through a Binary Matrix

## Problem Given a binary matrix where `1` is traversable and `0` is blocked, return every path from the top-left cell to the bottom-right cell. A move may go only right or down. Represent each path as a string of `R` and `D`, and return paths in lexicographic order. ### Function Contract Implement `allRightDownPaths(grid)`. ### Constraints & Assumptions - `1 <= rows, columns <= 10`. - Every row has the same length. - Cells contain only `0` or `1`. - If the start or destination is blocked, return an empty list. - Path output can be exponential; the small dimensions and output size are intentional. ### Clarifying Questions to Ask - May a path revisit a cell? Right/down movement makes revisiting impossible. - What represents a path on a `1 x 1` open grid? The empty string. - Which order is required? Lexicographic order with `D` before `R` under ordinary character ordering; explore down before right. - Should coordinates also be returned? No, move strings only. ```hint Backtrack one route buffer Append a move, recurse if the destination cell is valid, then remove that move before exploring the next branch. ``` ### Example ```text grid = [ [1, 1, 1], [1, 0, 1], [1, 1, 1] ] output = ["DDRR", "RRDD"] ``` ### Evaluation Focus - Rejects blocked endpoints and out-of-bounds moves. - Produces every valid route exactly once. - Maintains the specified output order without a required final sort. - Uses `O(rows + columns)` traversal stack space beyond the output. ### Extensions to Discuss 1. How would you count paths without enumerating them? 2. How would movement in four directions change cycle handling? 3. How would you return only the lexicographically first valid path?