Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Problem

Submissions

Hints & solutions

Discuss

Rat In a Maze

Hard

0/120

44 upvotes

Problem statement

You are given a N*N maze with a rat placed at 'mat[0][0]'. Find all paths that rat can follow to reach its destination i.e. mat[N-1][N-1]. The directions in which the rat can move are 'U'(up), 'D'(down), 'L' (left), 'R' (right).

In the given maze, each cell can have a value of either 0 or 1. Cells with a value of 0 are considered blocked, which means the rat cannot enter or traverse through them. On the other hand, cells with a value of 1 are open, indicating that the rat is allowed to enter and move through those cells.

Example:

mat:{{1, 0, 0, 0},
     {1, 1, 0, 1}, 
     {1, 1, 0, 0},
     {0, 1, 1, 1}}

All possible paths are:
DDRDRR (in red)
DRDDRR (in green)

Detailed explanation ( Input/output format, Notes, Images )

Input Format

The first line of input contains an integer 'N' denoting the rows and columns of a matrix
The next N lines of input contain N space-separated integers representing the type of the cell.

Output Format :

The output contains all the path in form of string. String consist of 'L' which means left, 'R' which means right, 'U' which means up and 'D' which means down. 
If there is no path, -1 is printed.

Note:-

You don’t need to print anything. Just implement the given function.

Sample Input 1 :

Sample Output 1 :

DDRR
RRDD

Explanation of Sample Input 1:

Only 2 path is possible.

Sample Input 2 :

2
1 1
1 0

Sample Output 2 :

-1

Explanation of Sample Input 2:

No path exists.

Constraints:

2 <= N <= 5
0 <= mati][j] <=1

Time Limit: 1sec

Hint 1

Think of a recursive solution

Approaches (1)

Approach 1

Recursive approach

Approach:

This approach uses a recursive backtracking approach to find all valid paths from the start to the destination in a rat maze. It explores all possible moves (up, down, left, right) from the current cell, while avoiding blocked cells and revisiting cells. If the destination cell is reached, the current path is added to the list of valid paths.

Algorithm:

function solve(i, j, path, matrix, row, column, ans):

if ‘i’ < 0 or ‘i’ >= ‘row’ or ‘j’ < 0 or ‘j’ >= ‘column’:
- return
if matrix[i][j] == 0:
- return
if ‘i’ == ‘row’ - 1 and j == ‘column’ - 1:
- ans.add(path) matrix[i][j] = 0
#Explore all possible moves
solve(i-1, j, path + 'U', matrix, row, column, ans) #Move up
solve(i+1, j, path + 'D', matrix, row, column, ans) #Move down
solve(i, j-1, path + 'L', matrix, row, column, ans) #Move left
solve(i, j+1, path + 'R', matrix, row, column, ans) #Move right
matrix[i][j] = 1

function ratMaze(mat):

path = ""
row = mat.length
column = mat[0].length
ans = empty list
solve(0, 0, path, mat, row, column, ans)
return ans

Time Complexity

O(3^(N^2)), where ‘N*N’ is the total number of cells in the maze.

The time complexity of the provided backtracking algorithm for the rat maze problem is exponential, specifically O(3^(N^2)), where ‘N*N’ is the total number of cells in the maze.

In the worst case, the algorithm explores all possible paths from the starting cell to the destination cell. At each cell, there are up to 3 possible directions the rat can take (excluding the cell it came from), as it cannot move diagonally. Therefore, the branching factor of the recursion is 3. Since the rat can visit each cell multiple times (due to backtracking), the algorithm explores a significant number of paths.

Considering an ‘N*N’ maze, the number of cells in the maze is N^2. In the worst case, the algorithm visits each cell at least once. Hence, the number of recursive calls and operations performed by the algorithm is approximately 3^(N^2).

Space Complexity

O(N^2), where ‘N*N’ is the total number of cells in the maze.

The space complexity of the provided backtracking algorithm for the rat maze problem is O(N^2), where ‘N*N’ is the total number of cells in the maze. The main contributors to the space complexity are the recursive call stack and the auxiliary space required to store the valid paths.

(100% EXP penalty)

Rat In a Maze

Shalini Srinivasan

Interview problems

easy to understand solution please like if it helps :)

void backtrack(int row,int col,string temp,vector<vector<int>>& vis,vector<string>& res, vector<vector<int>> &mat){
    int rows = mat.size();
    int cols = mat[0].size();
    if(row < 0 || col < 0 || row >= rows || col >= cols || mat[row][col] == 0 || vis[row][col] == 1)return;
    if(row == rows -1 && col == cols-1){
        res.push_back(temp);
        return;
    }

    vis[row][col] = 1;
    backtrack(row+1, col, temp+"D",vis, res, mat);
    backtrack(row, col+1, temp+"R",vis ,res, mat);
    backtrack(row-1, col, temp+"U", vis,res, mat);
    backtrack(row, col-1, temp+"L", vis,res, mat);
    vis[row][col] = 0;


}

vector<string> ratMaze(vector<vector<int>> &mat) {
    // Write your code here.
    if(mat[mat.size()-1][mat[0].size()-1] != 1)return {};
    string temp = "";
    vector<string> res;
    vector<vector<int>> vis(mat.size(),vector<int>(mat[0].size(),0));
    backtrack(0,0,temp,vis,res,mat);
    // if(res.size() == 0)return;
    return res;
}

78 views

0 replies

0 upvotes

Raj Mehra

Interview problems

simple solution

void findPathHelper(int i, int j, vector < vector < int >> & a, int n, vector < string > & ans, string move,

vector < vector < int >> & vis) {

if (i == n - 1 && j == n - 1) {

ans.push_back(move);

return;

}

// downward

if (i + 1 < n && !vis[i + 1][j] && a[i + 1][j] == 1) {

vis[i][j] = 1;

findPathHelper(i + 1, j, a, n, ans, move + 'D', vis);

vis[i][j] = 0;

}

// left

if (j - 1 >= 0 && !vis[i][j - 1] && a[i][j - 1] == 1) {

vis[i][j] = 1;

findPathHelper(i, j - 1, a, n, ans, move + 'L', vis);

vis[i][j] = 0;

}

// right

if (j + 1 < n && !vis[i][j + 1] && a[i][j + 1] == 1) {

vis[i][j] = 1;

findPathHelper(i, j + 1, a, n, ans, move + 'R', vis);

vis[i][j] = 0;

}

// upward

if (i - 1 >= 0 && !vis[i - 1][j] && a[i - 1][j] == 1) {

vis[i][j] = 1;

findPathHelper(i - 1, j, a, n, ans, move + 'U', vis);

vis[i][j] = 0;

}

vector<string> ratMaze(vector<vector<int>> &mat) {

int n=mat.size();

vector<string>ans;

vector<vector<int>>vis(n, vector < int > (n, 0));

if (mat[0][0] == 1) findPathHelper(0, 0, mat, n, ans, "", vis);

return ans;

}

134 views

2 replies

0 upvotes

Abhay Vishwakarma

Interview problems

most optimal using hashing and backtracking

void solve(int r,int c,string &path,vector<string>&ans,vector<vector<int>>&arr,int n,vector<vector<int>>&visit){
    if(r == n-1 && c == n-1){
        ans.push_back(path);
        return;
    }
    int x[] = {-1,0,1,0};
    int y[] = {0,1,0,-1};
    char dir[] = {'U','R','D','L'};
    for(int k=0;k <= 3;k++){
        int nr = r + x[k],nc = c + y[k];
        if(nr < n && nr >= 0 && nc < n && nc >= 0 && visit[nr][nc]==0 && arr[nr][nc]==1){
            visit[nr][nc] = 1;
            path += dir[k];
            solve(nr,nc,path,ans,arr,n,visit);
            path.pop_back();
            visit[nr][nc] = 0;
        }
    }
}
vector<string> ratMaze(vector<vector<int>> &m) {
      string path = "";
      int n=m.size();
        vector<string>ans;
        if(m[0][0] == 0 || m[n-1][n-1] == 0) return ans;
        vector<vector<int>>visit(n,vector<int>(n,0));
        visit[0][0] = 1;
        solve(0,0,path,ans,m,n,visit);
        return ans;
}

163 views

0 replies

0 upvotes

Can Ozturk

Interview problems

easy java code

public static List<String> ratMaze(int[][] mat) {
    List<String> retval = new ArrayList<>();

    helper(retval, mat, "", 0, 0);

    return retval;
}

private static void helper(List<String> retval, int[][] mat, String sb, int i, int j) {
    if(i < 0 || i >= mat.length || j < 0 || j >= mat[0].length || mat[i][j] == 0) return;

    if(i == mat.length - 1 && j == mat[0].length - 1) {
        retval.add(sb);
        return;
    }

    mat[i][j] = 0;

    // up
    helper(retval, mat, sb + "U", i - 1, j);

    // down
    helper(retval, mat, sb + "D", i + 1, j);

    // left
    helper(retval, mat, sb + "L", i, j - 1);

    // right
    helper(retval, mat, sb + "R", i, j + 1);

    mat[i][j] = 1;
}

117 views

0 replies

0 upvotes

Amit Kumar

Interview problems

Rat In a Maze | Cleaner code | Easy to Understand

void solve(vector<vector<int>> &mat,int row, int col, string &s, vector<string> &ans){

if(row <0 || col <0 || row >=mat.size() || col >=mat.size() || mat[row][col]==0 || mat[row][col]==-1){

return;

}

if(row==mat.size()-1 && col==mat.size()-1){

ans.push_back(s);

return ;

}

mat[row][col]=-1;

s += 'U';

solve(mat,row-1,col,s,ans); //up

s.pop_back();

s += 'R';

solve(mat,row,col+1,s,ans); //right

s.pop_back();

s += 'L';

solve(mat,row,col-1,s,ans); //left

s.pop_back();

s += 'D';

solve(mat,row+1,col,s,ans); // down

s.pop_back();

mat[row][col]=1;

}

vector<string> ratMaze(vector<vector<int>> &mat) {

string s="";

vector<string> ans;

solve(mat,0,0,s,ans);

if(ans.size()==0){

ans.push_back("-1");

return ans;

}

return ans;

}

207 views

0 replies

2 upvotes

Harsh Vardhan Singh

Interview problems

Recursion

bool issafe(int x,int y, int n, vector<vector<int>> visited,vector<vector<int>> &mat){

if((x>=0 && x<n) && (y>=0 && y<n) && visited[x][y]==0 && mat[x][y]==1 ){

return true;

}

else{

return false;

}

void solve(vector<vector<int>> &mat,int n,vector<string> &ans,int x,int y,string path,vector<vector<int>> visited){

if(x==n-1&&y==n-1){

ans.push_back(path);

return;

}

visited[x][y]=1;

//down

int newx=x+1;

int newy=y;

if(issafe(newx,newy,n,visited,mat)){

path.push_back('D');

solve(mat, n, ans, newx, newy, path, visited);

path.pop_back();

}

//left

newx=x;

newy=y-1;

if(issafe(newx,newy,n,visited,mat)){

path.push_back('L');

solve(mat, n, ans, newx, newy, path, visited);

path.pop_back();

}

//right

newx=x;

newy=y+1;

if(issafe(newx,newy,n,visited,mat)){

path.push_back('R');

solve(mat, n, ans, newx, newy, path, visited);

path.pop_back();

}

//UP

newx=x-1;

newy=y;

if(issafe(newx,newy,n,visited,mat)){

path.push_back('U');

solve(mat, n, ans, newx, newy, path, visited);

path.pop_back();

}

visited[x][y]=0;

}

vector<string> ratMaze(vector<vector<int>> &mat) {

// Write your code here.

int n=mat.size();

vector<string> ans;

if(mat[0][0]==0){

return ans;

}

int srcx=0;

int srcy=0;

vector<vector<int>> visited(n,vector<int>(n,0));

string path="";

solve(mat,n,ans,srcx,srcy,path,visited);

return ans;

}

174 views

0 replies

0 upvotes

OMM PRATIK PARIDA

Interview problems

c++ simplified code

void solve(vector<vector<int>> &mat,string &path,vector<string> &ans,int i,int j){

if(i<0 || j<0 || j>=mat.size() || i>=mat.size() || mat[i][j] == -1 || mat[i][j] == 0){

return;

}

if(i == mat.size()-1 && j==mat.size()-1){

ans.push_back(path);

return;

}

int x[4] = {1,-1,0,0};

int y[4] = {0,0,1,-1};

for(int index = 0;index<4;index++){

if(x[index]==0){

if(y[index]==1) path+='R';

else path+='L';

}

else{

if(x[index]==1) path+='D';

else path+='U';

}

int a = mat[i][j];

mat[i][j] =-1;

solve(mat,path,ans,i+x[index],j+y[index]);

mat[i][j] = a;

path.pop_back();

}

vector<string> ratMaze(vector<vector<int>> &mat) {

string path = "";

vector<string> ans;

solve(mat,path,ans,0,0);

return ans;

}

161 views

0 replies

1 upvote

Dhananjay Nathawat

Interview problems

Easy c++ solution

vector<int>genNewCords(int i ,int j,char direction){

//find where will be the next cordinates based on direction we go

int newI=-1; int newJ=-1;

if(direction =='D'){

newI=i+1;

newJ=j;

}

else if(direction == 'L'){

newI = i;

newJ = j-1;

}

else if(direction == 'R'){

newI = i;

newJ = j+1;

}

else{

newI = i-1;

newJ = j;

}

return {newI,newJ};

}

bool checkPossible(int i ,int j,vector<vector<int>> &mat,vector<vector<int>> &visited){

//check if is possible to gow in to newCordinates

int size = mat.size();

if((i<size && i>=0) && (j<size && j>=0)){

if(mat[i][j]==0 ||visited[i][j] == 1){

return false;

}

else {

return false;

}

return true;

}

void ratMazeRecursion(int i,int j,vector<vector<int>> &mat, vector<vector<int>> &visited, vector<string>&ans,string &path){

vector<char>directions = {'D','L','R','U'};

if(i==mat.size()-1 && j == mat.size()-1){

ans.push_back(path);

return;

}

for(int d = 0; d<directions.size();d++){

vector<int>newChords = genNewCords(i, j, directions[d]);

if(checkPossible(newChords[0],newChords[1],mat,visited)){

visited[i][j] = 1;

path.push_back(directions[d]);

ratMazeRecursion(newChords[0], newChords[1], mat, visited, ans, path);

visited[i][j] = 0;

path.pop_back();

}

vector<string> ratMaze(vector<vector<int>> &mat) {

// Write your code here.

vector<string>ans;

string path;

int n = mat.size();

vector<vector<int>> visited(n, vector<int>(n, 0));

ratMazeRecursion(0, 0, mat, visited, ans, path);

return ans;

}

80 views

0 replies

0 upvotes

Aditya Kumar Tiwari

Interview problems

Rat in a maze || Striver || 100% beats

#include <iostream>

void solve(int i, int j, std::vector<std::vector<int>>& mat, int n, std::vector<std::string>& ans, std::string temp, std::vector<std::vector<int>>& vis, int di[], int dj[]) {
    // base
    if (i == n - 1 && j == n - 1) {
        ans.push_back(temp);
        return;
    }
    std::string dir = "DLRU";
    for (int ind = 0; ind < 4; ind++) {
        int nexti = i + di[ind];
        int nextj = j + dj[ind];
        if (nexti >= 0 && nextj >= 0 && nexti < n && nextj < n && !vis[nexti][nextj] && mat[nexti][nextj] == 1) {
            vis[i][j] = 1;
            solve(nexti, nextj, mat, n, ans, temp + dir[ind], vis, di, dj);
            vis[i][j] = 0;
        }
    }
}

std::vector<std::string> ratMaze(std::vector<std::vector<int>>& mat) {
    int n = mat.size();
    std::vector<std::string> ans;
    std::vector<std::vector<int>> vis(n, std::vector<int>(n, 0));
    std::string temp = "";
    int di[] = {1, 0, 0, -1};
    int dj[] = {0, -1, 1, 0};
    if (mat[0][0] == 1) {
        solve(0, 0, mat, n, ans, temp, vis, di, dj);
    }
    return ans;
}

programming

beginners

173 views

0 replies

2 upvotes

Tushar Gahlaut

Interview problems

Easy C++ DFS Path Finder Solution


//Idea is to traverse in every direction

    void solve(vector<string> &ans, string path, vector<vector<int>> &maze, int row, int col, int n){
        if(row==(n-1) && col==(n-1) && maze[n-1][n-1]!=0){
            ans.push_back(path);
            return ;
        }
        if(row<0 || col<0 || row>=n || col>=n || maze[row][col]==0){
            return ;
        }
        maze[row][col]=0;
        solve(ans, path+'U',maze,row-1,col,n);
        solve(ans, path+'D',maze,row+1,col,n);
        solve(ans, path+'L',maze,row,col-1,n);
        solve(ans, path+'R',maze,row,col+1,n);
        maze[row][col]=1;
    }

vector<string> ratMaze(vector<vector<int>> &mat) {
    int n = mat.size();
     vector<string> ans;
        string path;
        solve(ans,path,mat,0,0,n);
        return ans;
}

103 views

0 replies

0 upvotes

Console