Rat in a Maze

Given an n by n grid of zeros and ones, return every path from the top-left cell to the bottom-right cell. A one is open and a zero is blocked. Move only up,…

Given an n by n grid of zeros and ones, return every path from the top-left cell to the bottom-right cell. A one is open and a zero is blocked. Move only up, down, left or right, and never visit a cell twice in the same path. Implement findPath(grid) and encode each path as a string of U, D, L and R moves. Return each legal path once, in any order. If either endpoint is blocked or the goal is unreachable, return an empty list, not -1.

- 2 <= n <= 5; the grid is square. - Every grid value is the integer 0 or 1. - Each path starts at (0, 0), ends at (n - 1, n - 1) and uses only open cells. - No cell can be reused within one path. Different paths may use the same cell.

Example 1: input grid = [[1,1],[1,1]]; output ["DR","RD"]. The two routes go down then right, or right then down.

Example 2: input grid = [[1,0],[1,0]]; output []. The destination is blocked, so no route exists.

Example 3: input grid = [[1,0,0,0],[1,1,0,1],[1,1,0,0],[0,1,1,1]]; output ["DDRDRR","DRDDRR"]. Two different corridors reach the goal without revisiting a cell.

Category: Recursion. Topic: recursion. Difficulty: Hard. Patterns: backtracking.