Problem Statement

Given a grid of dimensions n x n. A rat is placed at coordinates (0, 0) and wants to reach at coordinates (n-1, n-1). Find all possible paths that rat can take to travel from (0, 0) to (n-1, n-1). The directions in which rat can move are 'U' (up) , 'D' (down) , 'L' (left) , 'R' (right).

The value 0 in grid denotes that the cell is blocked and rat cannot use that cell for travelling, whereas value 1 represents that rat can travel through the cell. If the cell (0, 0) has 0 value, then mouse cannot move to any other cell.

Examples

Example 1:

Input: grid = [
               [1, 0, 0, 0],
               [1, 1, 0, 1],
               [0, 1, 0, 0],
               [1, 1, 1, 1]
              ]

Output: [
         "DDRDRR",
         "DRDDRR"
        ]
        
Explanation:

There are two paths from the top-left corner to the bottom-right corner:

Path 1: Move down (D), down (D), right (R), down (D), right (R), right (R) — giving "DDRDRR"
Path 2: Move down (D), right (R), down (D), down (D), right (R), right (R) — giving "DRDDRR"

Example 2:

Input: grid = [
               [1, 0],
               [1, 0]
              ]

Output: ["-1"]

Explanation:
There is no valid path from the start to the destination, so the output is ["-1"].

Example 3:

Input: grid = [
               [1, 0, 0],
               [1, 1, 0],
               [0, 1, 1]
              ]
Output: [
         "DRDR"
        ]

Different Approaches

1️⃣ Backtracking

Intuition:

This maze-solving process can be translated into a recursive function. The starting position in the maze is equivalent to the initial call of the recursive function. Each possible direction (up, down, left, right) corresponds to a recursive call exploring that direction. Upon finding a valid move (an open path), the current path is updated and the function proceeds to the next step. When a dead end is encountered (a blocked path), the function backtracks to the previous step and explores alternative directions. This recursive exploration continues until the destination is reached, recording all possible paths.

Approach:

1. Start from the initial position (0,0) in the grid.
2. Check if the current position is the destination. If so, add the current path to the results.
3. If the current cell is blocked (value is 0), return.
4. Mark the current cell as visited by setting its value to 0.
5. Explore all possible directions (up, down, left, right) from the current cell:
   • Move up if the current cell is not in the topmost row.
   • Move left if the current cell is not in the leftmost column.
   • Move down if the current cell is not in the bottommost row.
   • Move right if the current cell is not in the rightmost column.
6. After exploring all directions, unmark the current cell by resetting its value to 1 to allow other paths to pass through it.
7. Repeat the above steps recursively until all possible paths are explored.
8. Sort the resulting paths alphabetically.

Code:

#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
    void findPaths(vector<vector<int>>& grid, vector<string>& result, string path, int n, int i, int j) {
        // Base Case: if we reach the bottom-right cell
        if (i == n - 1 && j == n - 1) {
            result.push_back(path);
            return;
        }

        // Validate the cell bounds and if it is unvisited and not blocked
        if (i < 0 || j < 0 || i >= n || j >= n || grid[i][j] == 0 || grid[i][j] == -1) {
            return;
        }

        // Mark the cell as visited
        int temp = grid[i][j];
        grid[i][j] = -1;

        // Recursively explore in a fixed order to maintain lexicographic order: Down, Right, Up, Left
        if (i + 1 < n) findPaths(grid, result, path + 'D', n, i + 1, j); // Down
        if (j + 1 < n) findPaths(grid, result, path + 'R', n, i, j + 1); // Right
        if (i - 1 >= 0) findPaths(grid, result, path + 'U', n, i - 1, j); // Up
        if (j - 1 >= 0) findPaths(grid, result, path + 'L', n, i, j - 1); // Left

        // Backtrack and restore the cell value
        grid[i][j] = temp;
    }

    vector<string> findPath(vector<vector<int>>& grid) {
        vector<string> result;
        int n = grid.size();
        if (grid[0][0] == 1) {  // Only proceed if starting cell is open
            findPaths(grid, result, "", n, 0, 0);
        }

        // If no path was found, return "-1" as a single result in the vector
        if (result.empty()) {
            result.push_back("-1");
        }

        return result;
    }
};

int main() {
    vector<vector<int>> grid = {
        {1, 0, 0, 0},
        {1, 1, 0, 1},
        {0, 1, 0, 0},
        {1, 1, 1, 1}
    };

    Solution sol;
    vector<string> paths = sol.findPath(grid);

    for (const string& path : paths) {
        cout << path << endl;
    }

    return 0;
}

Explanation:

1. Base Case: If we reach the destination (n-1, n-1), we add the path to result.
2. Boundary and Condition Check: Ensure we’re within bounds, and check if the cell is open and unvisited.
3. Mark Cell as Visited: Temporarily mark the current cell as visited (-1) to prevent revisiting.
4. Recursive Calls in Lexicographic Order: Explore in the order Down, Right, Up, Left to ensure paths are in lexicographic order.
5. Backtrack: Restore the cell's original value after exploring to allow other paths.

Complexity Analysis:

• Time Complexity: O(4 n^2)
  • Each cell has at most 4 possible moves (down, right, up and left).
  • For a grid of size n*n, the maximum number of moves the rat could theoretically make would be 4 ^ n*n, which would involve visiting every cell in every possible combination.
  • However, the use of backtracking and marking cells as visited restricts revisiting cells within a single path, significantly reducing the number of redundant calls.
  • Therefore, the upper bound on the time complexity can be estimated as: O(4^n*n).
• Space Complexity: O(n^2)
  • Recursion stack: At any given time, the recursion stack can go as dep as n * n, as each cell may lead to recursive call.