Rat in a Maze
You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4): 1 0 0 0 1 1 0 0 1 1 0 0 0 1 1 1 Expected Output: DDRDRR DRDDRR i.e. Path-1: DDRDRR and Path-2: DRDDRR The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.

Input format:

The first line contains an integer 'N', which denotes the dimensions of the square matrix (maze). Then 'N' lines follow. Each line contains 'N' space-separated integers denoting the values which would either be 0 denoting a blocked path or 1 denoting the available path in the maze, respectively.

Output format:

For the given maze, print the vector/list of strings representing all the possible paths that the rat can take to reach from source to destination in the maze in sorted order. Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

2

Question

Rat in a Maze

You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a square matrix of order 'N' * 'N' where the cells with value 0 represent the maze’s blocked locations while value 1 is the open/available path that the rat can take to reach its destination. The rat's destination is at ('N' - 1, 'N' - 1). Your task is to find all the possible paths that the rat can take to reach from source to destination in the maze. The possible directions that it can take to move in the maze are 'U'(up) i.e. (x, y - 1) , 'D'(down) i.e. (x, y + 1) , 'L' (left) i.e. (x - 1, y), 'R' (right) i.e. (x + 1, y).

Note:

Here, sorted paths mean that the expected output should be in alphabetical order.

For Example:

Given a square matrix of size 4*4 (i.e. here 'N' = 4):
1 0 0 0
1 1 0 0
1 1 0 0
0 1 1 1 
Expected Output:
DDRDRR DRDDRR 
i.e. Path-1: DDRDRR and Path-2: DRDDRR

The rat can reach the destination at (3, 3) from (0, 0) by two paths, i.e. DRDDRR and DDRDRR when printed in sorted order, we get DDRDRR DRDDRR.

Input format:

The first line contains an integer 'N', which denotes the dimensions of the square matrix (maze).

Then 'N' lines follow. Each line contains 'N' space-separated integers denoting the values which would either be 0 denoting a blocked path or 1 denoting the available path in the maze, respectively.

Output format:

For the given maze, print the vector/list of strings representing all the possible paths that the rat can take to reach from source to destination in the maze in sorted order.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

2 <= N <= 5
0 <= MATRIX[i][j] <= 1

Where N is the size of the square matrix.

Time Limit: 1sec

Accepted Answer

Bactracking

Approach: We can start the traversal of the paths from the rat’s starting position, i.e. (0,0) keeping track of the visited cells during the traversal. We will recursively go through all the paths possible until the last index of the grid (destination) is reached, and add the path information using which the rat successfully reached the end.

Algorithm is as follows:

Take the starting position of the rat as (0, 0) and start traversing the valid cells (which are unblocked, i.e. with value 1) through adjacent cells in the following order Down -> Left -> Right -> Up so that we can automatically get sorted paths in alphabetical order.
Create another matrix/grid called ‘VISITED’ to keep track of all visited and unvisited cells
Recursively look for the valid set of paths possible from the starting cell until we reach the destination or an invalid cell. We keep setting the respective ‘VISITED’ matrix/grid value of the cell to true. I.e.:-
If the move is possible, then move to that cell while storing the character corresponding to the move, i.e. either (D, L, R, U) and recursively start looking for a valid move until the destination (i.e. (n - 1, n - 1)) is reached by the rat.
Keep marking the cells as visited. When all the paths possible are traversed from that cell, unmark that cell for other different paths and remove the character from the path formed.
As soon as the last index of the grid(bottom right), our destination is reached, we store the traversed path information in a vector/list.

Space Complexity: O(n^2)Explanation:

O(N^2), where N is the dimension of the square matrix.

As there can be at most N^2 cells in the answer for each possible path available for each cell with N^2 cells in total, so the space complexity is also O(N^2).

Time Complexity: OtherExplanation:

O(3^(N^2)), where N is the dimension of the square matrix.

Now, since there are N^2 cells in total and from each cell, there can only be three unvisited neighbouring cells. So the time complexity O(3^(N^2)).

Java (SE 1.8)

/*
    Time complexity: O(3^(N^2))
    Space Complexity: O(N^2))

    where N is the size of array/list ARR.
*/

import java.util.ArrayList;

public class Solution {

    public static boolean isValidMove(int y, int x, int[][] arr, boolean[][] visited) {

        if (x == -1 || x == arr.length || y == -1 || y == arr.length || visited[y][x] || arr[y][x] == 0) {
            return false;
        }

        return true;
    }

    public static void printPathUtil(int[][] arr, int y, int x, String path, ArrayList< String > pathList, boolean[][] visited) {
        
        // This will check the initial point(i.e. (0, 0)) to start the paths.
        if (x == -1 || x == arr.length || y == -1 || y == arr.length || visited[y][x] || arr[y][x] == 0) {
            return;
        }

        // If reach the last cell (n-1, n-1) then store the path and return.
        if (x == arr.length - 1 && y == arr.length - 1) {
            pathList.add( new String(path) );
            return;
        }

        visited[y][x] = true;

        // Try for all the 4 directions (down, left, right, up) 
        // in the given order to get the paths in lexicographical order.

        if (isValidMove(y + 1, x, arr, visited)) {
            path += "D";
            printPathUtil(arr, y + 1, x, path, pathList, visited);
            path = path.substring(0, path.length() - 1);
        }

        if (isValidMove(y, x - 1, arr, visited)) {
            path += "L";
            printPathUtil(arr, y, x - 1, path, pathList, visited);
            path = path.substring(0, path.length() - 1);
        }

        if (isValidMove(y, x + 1, arr, visited)) {
            path += "R";
            printPathUtil(arr, y, x + 1, path, pathList, visited);
            path = path.substring(0, path.length() - 1);
        }

        if (isValidMove(y - 1, x, arr, visited)) {
            path += "U";
            printPathUtil(arr, y - 1, x, path, pathList, visited);
            path = path.substring(0, path.length() - 1);
        }

        // Mark the cell as unvisited for other possible paths.
        visited[y][x] = false;

    }

    public static ArrayList < String > findSum(int[][] arr, int n) {

        // ArrayList to store the answer.
        ArrayList < String > possiblePaths = new ArrayList < String >();
        String path = "";

        boolean[][] visited = new boolean[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                visited[i][j] = false;
            }
        }

        printPathUtil(arr, 0, 0, path, possiblePaths, visited);

        return possiblePaths;
    }
}

C++ (g++ 5.4)

/*
    Time complexity: O(3^(N^2))
    Space Complexity: O(N^2)

    where N is the size of array/list ARR.
*/

bool isValidMove(int y, int x, vector < vector < int >> & arr, vector < vector < bool >> & visited) {

    if (x == -1 || x == arr.size() || y == -1 || y == arr.size() || visited[y][x] || arr[y][x] == 0) {
        return false;
    }

    return true;
}

void printPathUtil(vector < vector < int >> & arr, int y, int x, string path, vector < string > & pathList, vector < vector < bool >> & visited) {
    
    // This will check the initial point(i.e. (0, 0)) to start the paths.
    if (x == -1 || x == arr.size() || y == -1 || y == arr.size() || visited[y][x] || arr[y][x] == 0) {
        return;
    }

    // If reach the last cell (n-1, n-1) then store the path and return.
    if (x == arr.size() - 1 and y == arr.size() - 1) {
        pathList.push_back(path);
        return;
    }

    visited[y][x] = true;

    // Try for all the 4 directions (down, left, right, up) 
    // in the given order to get the paths in lexicographical order.

    if (isValidMove(y + 1, x, arr, visited)) {
        path += "D";
        printPathUtil(arr, y + 1, x, path, pathList, visited);
        path.pop_back();
    }

    if (isValidMove(y, x - 1, arr, visited)) {
        path += "L";
        printPathUtil(arr, y, x - 1, path, pathList, visited);
        path.pop_back();
    }

    if (isValidMove(y, x + 1, arr, visited)) {
        path += "R";
        printPathUtil(arr, y, x + 1, path, pathList, visited);
        path.pop_back();
    }

    if (isValidMove(y - 1, x, arr, visited)) {
        path += "U";
        printPathUtil(arr, y - 1, x, path, pathList, visited);
        path.pop_back();
    }

    // Mark the cell as unvisited for other possible paths.
    visited[y][x] = false;

}

vector < string > searchMaze(vector < vector < int >> & arr, int n) {

    // Vector to store the answer.
    vector < string > possiblePaths;
    string path = "";

    vector < vector < bool >> visited(n, vector < bool > (n, false));

    printPathUtil(arr, 0, 0, path, possiblePaths, visited);

    return possiblePaths;
}

Python (3.5)

'''
    Time complexity: O(3^(N^2))
    Space Complexity: O(N^2)

    where N is the size of array/list ARR.
'''

def isValidMove(y, x, arr, visited):
    
    if x == -1 or x == len(arr) or y == -1 or y == len(arr) or visited[y][x] or arr[y][x] == 0:
        return False
        
    return True

def printPathUtil(arr, y, x, path, pathList, visited):
    
    # This will check the initial point(i.e. (0, 0)) to start the paths.
    if x == -1 or x == len(arr) or y == -1 or y == len(arr) or visited[y][x] or arr[y][x] == 0:
        return
    
    # If reach the last cell (n-1, n-1) then store the path and return.
    if x == len(arr) - 1 and y == len(arr) - 1:
        pathList.append(path)
        return
    
    visited[y][x] = True
    
    # Try for all the 4 directions (down, left, right, up)
    # in the given order to get the paths in lexicographical order.
    
    if isValidMove(y + 1, x, arr, visited):
        path += 'D'
        printPathUtil(arr, y + 1, x, path, pathList, visited)
        path = path[:-1]
    
    if isValidMove(y, x - 1, arr, visited):
        path += 'L'
        printPathUtil(arr, y, x - 1 , path, pathList, visited)
        path = path[:-1]
    
    if isValidMove(y, x + 1, arr, visited):
        path += 'R'
        printPathUtil(arr, y, x + 1 , path, pathList, visited)
        path = path[:-1]
    
    if isValidMove(y - 1, x, arr, visited):
        path += 'U'
        printPathUtil(arr, y - 1, x, path, pathList, visited)
        path = path[:-1]
    
    # Mark the cell as unvisited for other possible paths.
    visited[y][x] = False


def searchMaze(arr, n):

    # List to store all the possible paths.
    possiblePaths = []
    path = ""
    visited = [[False for _ in range(n)]
                      for _ in range(n)]

    printPathUtil(arr, 0, 0, path, possiblePaths, visited)
    
    return possiblePaths

Note:

For Example:

Input format:

Output format:

Note:

Constraints:

Top JUSPAY Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern