Rat in a Maze Problem - I

Time: O(4^(n*m))

Space: O(n*m)

Intuition

Backtracking: from (0,0), try moving Down/Left/Right/Up (in any order). Mark cell as visited to avoid cycles. Record path when (n-1,n-1) is reached. Backtrack by unmarking.

Algorithm

1DFS(r,c,path): if (r,c)==(n-1,n-1): add path to results.
2For each direction (D,L,R,U) in sorted order: compute (nr,nc). If valid, unvisited, and maze[nr][nc]==1: mark, recurse, unmark.

Example Walkthrough

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

1.Path DDRDRR: (0,0)â†’(1,0)â†’(2,0)â†’(2,1)â†’(3,1)â†’(3,2)â†’(3,3). Valid!

Output: ["DDRDRR"]

Common Pitfalls

•Add directions in sorted order (D,L,R,U) to get paths in lexicographic order.

Rat in a Maze Problem - I.java

Java

// Approach: Backtracking. Explore all 4 directions from current cell, mark visited, backtrack on dead ends.
// Time: O(4^(n*m)) Space: O(n*m)
import java.util.*;

class Solution {
    public ArrayList<String> findPath(int[][] mat) {
        int n = mat.length;
        ArrayList<String> ans = new ArrayList<String>();
        int[][] vis = new int[n][n];
        if (mat[0][0] == 1)
            find(0, 0, mat, n, ans, "", vis);

        return ans;
    }

    private static void find(int i, int j, int[][] a, int n, ArrayList<String> ans, String move, int[][] vis) {
        if (i == n - 1 && j == n - 1) {
            ans.add(move);
            return;
        }

        // down
        if (i + 1 < n && vis[i + 1][j] == 0 && a[i + 1][j] == 1) {
            vis[i][j] = 1;
            find(i + 1, j, a, n, ans, move + 'D', vis);
            vis[i][j] = 0;
        }

        // left
        if (j - 1 >= 0 && vis[i][j - 1] == 0 && a[i][j - 1] == 1) {
            vis[i][j] = 1;
            find(i, j - 1, a, n, ans, move + 'L', vis);
            vis[i][j] = 0;
        }

        // right
        if (j + 1 < n && vis[i][j + 1] == 0 && a[i][j + 1] == 1) {
            vis[i][j] = 1;
            find(i, j + 1, a, n, ans, move + 'R', vis);
            vis[i][j] = 0;
        }

        // up
        if (i - 1 >= 0 && vis[i - 1][j] == 0 && a[i - 1][j] == 1) {
            vis[i][j] = 1;
            find(i - 1, j, a, n, ans, move + 'U', vis);
            vis[i][j] = 0;
        }
    }
}

Was this solution helpful?