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

Rat In a Maze All Paths

Moderate
0/80
Average time to solve is 40m
profile
Contributed by
260 upvotes
Asked in companies
VisaExpedia GroupHexaware Technologies

Problem statement

You are given a 'N' * 'N' maze with a rat placed at 'MAZE[0][0]'. Find and print all paths that rat can follow to reach its destination i.e. 'MAZE['N' - 1]['N' - 1]'. Rat can move in any direc­tion ( left, right, up and down).

Value of every cell in the 'MAZE' can either be 0 or 1. Cells with value 0 are blocked means the rat can­not enter into those cells and those with value 1 are open.

Detailed explanation ( Input/output format, Notes, Images )
Input Format:
The first line of input contains an integer 'N' representing the dimension of the maze.

The next 'N' lines of input contain 'N' space-separated integers representing the type of the cell.
Output Format :
For each test case, return the path from the start position to the destination position and only cells that are part of the solution path should be 1, rest all cells should be 0.

Output for every 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:
1 <= N <= 10
0 <= MAZE[i][j] <=1

Where 'MAZE[i][j]' denotes the value in the cell of 'MAZE'.

Time Limit: 1 sec
Sample Input 1 :
3
1 0 1
1 0 1
1 1 1
Sample Output 1 :
1 0 0 1 0 0 1 1 1 
Explanation for Sample Output 1:
Only 1 path is possible which contains coordinate < (1,1), (2,1), (3,1), (3,2) and (3,3) >

So our path matrix will look like this:

1 0 0
1 0 0
1 1 1

Which is returned from left to right and then top to bottom in one line.
Sample Input 2 :
2
1 0
0 1
Sample Output 2 :
 [Blank]
Explanation for Sample Output 2:
As no path is possible to the last cell, a blank vector will be returned and nothing is printed.
Hint

Try every possible path using recursion and backtracking.

Approaches (1)
Backtracking Approach

Initialize, all the cells of the solution matrix used to print the path matrix to 0. First, you cannot make use of the existing maze to print the solution maze as you have to distinguish b/w 1 of maze or 1 of ‘SOLUTION matrix.

 

Form a recursive function, which will follow a path and check if the path reaches the destination or not. If the path does not reach the destination then backtrack and try other paths. But in case it reaches the destination print the current ‘SOLUTION’ matrix.

 

The steps are as follows:

 

f('i', ‘j'):

  • If rat reaches the destination, print the solution matrix.
  • Else:
    • If not valid('MAZE[i][j]' ) return
    • Else ‘SOLUTION[i][j]' =1
    • f(i-1,j) ;  f(i+1,j) , f(i, j-1) , f(i,j+1) // Recursive calls
    • ‘SOLUTION[i][j]' = 0    // Backtracking
Time Complexity

O(4 ^ (N ^ 2)), Where ‘N’ is the dimension of the matrix.

 

Since we can call 4 recursive calls from each cell in ‘N’ * ‘N’ board, Thus the time complexity will be O(4 ^ (N ^ 2)).

Space Complexity

O(N * N), Where ‘N’ is the dimension of the matrix.

  

Since the extra space used to create 'SOLUTION matrix of size N * N. Thus the space complexity will be O(N * N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Rat In a Maze All Paths
All tags
Sort by
Search icon

Interview problems

easy cpp

#include <bits/stdc++.h>

 

void TPC(int i, int j, vector<vector<int>> &maze,

           vector<vector<int>> &ans, vector<int> &part, int n) {

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

  {

    part[i * n + j] = 1;

    ans.push_back(part);

    return;

  }

  if (i > n - 1 || i < 0 || j > n - 1 || j < 0) {

    return;

  }

  if (maze[i][j] == 0 || part[i * n + j] == 1)

    return;

  part[i * n + j] = 1;

  TPC(i - 1, j, maze, ans, part, n);

  TPC(i + 1, j, maze, ans, part, n);

  TPC(i, j - 1, maze, ans, part, n);

  TPC(i, j + 1, maze, ans, part, n);

  part[i * n + j] = 0;

}

 

vector<vector<int>> ratInAMaze(vector<vector<int>> &maze, int n) {

  if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0)

    return {};

  vector<int> part(n * n, 0);

  vector<vector<int>> ans;

  TPC(0, 0, maze, ans, part, n);

  return ans;

}

44 views
0 replies
0 upvotes

Interview problems

Rat in a Maze all Paths

#include <bits/stdc++.h> 

 

void solve(int row, int col, vector<vector<int>> &maze, vector<vector<int>> &ans, vector<int> &sub, int n){

  if(row == n-1 && col == n-1)

  {

    sub[row*n + col] = 1;

    ans.push_back(sub);

    return;

  }

 

  if (row > n - 1 || row < 0 || col > n - 1 || col < 0){

      return;

  }

 

  if(maze[row][col] == 0 || sub[row*n + col] == 1)

    return;

  

  sub[row*n + col] = 1;

 

  // up

  solve(row-1, col, maze, ans, sub, n);

 

  // down

  solve(row+1, col, maze, ans, sub, n);

 

  // left

  solve(row, col-1, maze, ans, sub, n);

  

  // right

  solve(row, col+1, maze, ans, sub, n);

 

  sub[row*n + col] = 0;

 

}

 

vector<vector<int> > ratInAMaze(vector<vector<int> > &maze, int n){

  if(maze[0][0] == 0 || maze[n-1][n-1] == 0)

    return {};

  

  vector<int> sub(n*n, 0);

  vector<vector<int>> ans;

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

  solve(0, 0, maze, ans, sub, n);

  return ans;

}

144 views
0 replies
1 upvote

Interview problems

Rat in a maze

#include <bits/stdc++.h> 

bool isValid(int x , int y , vector < vector<bool> > &visited , vector < vector <int> > &maze , int n) {

 

  if(x < 0 || x >= n ) return false;

 

  if(y < 0 || y >= n) return false;

 

  if(visited[x][y] == 1) return false;

 

  if(maze[x][y] == 0) return false;

 

  return true;

 

}

// functiom to find all possible paths

void allPaths(int x , int y , vector < vector <int> > &maze , vector < vector <bool> > &visited , vector <vector<int> > &ans , int n) {

 

  // base case 

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

 

    visited[x][y] = 1;

 

    int nrows = visited . size();

 

    int ncols = visited[0] . size();

 

    vector<int> temp;

 

    for(int i = 0; i < nrows; i++) {

 

      for(int j = 0; j < ncols; j++) {

 

        temp . push_back(visited[i][j]);

 

      }

 

    }

 

    ans . push_back(temp);

  return ;

  }

 

  // up x - 1 , y

  // down : x + 1 , y

  // left :x , y - 1

  // right : x , y + 1

  // traversing all the paths and assume that recursion get the answer

  // check whether particular cell is valid or not

  // for up

 

  if(isValid(x - 1 , y , visited , maze , n)) {

 

    visited[x - 1][y] = 1;

 

    allPaths( x - 1,  y,  maze, visited,  ans ,n);

 

  }

 

  // for down

  if(isValid(x + 1 , y , visited , maze , n)) {

 

    visited[x + 1][y] = 1;

 

    allPaths( x + 1,  y,  maze, visited,  ans , n);

 

  }

 

  // for left

  if(isValid(x  , y - 1 , visited , maze , n)) {

 

    visited[x][y - 1] = 1;

 

    allPaths( x ,  y - 1,  maze, visited,  ans , n);

 

  }

 

  // for right

  if(isValid(x  , y + 1 , visited , maze , n)) {

 

    visited[x][y + 1] = 1;

 

    allPaths( x,  y + 1,  maze, visited,  ans , n);

 

  }

 

  //backtracking steps

  visited[x][y] = 0;

 

}

vector<vector<int> > ratInAMaze(vector<vector<int> > &maze, int n){

 

  // visited array which keeps track of the visited position

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

 

  // ans array which stores all the paths

  vector < vector<int> > ans;

    allPaths(0, 0, maze, visited, ans , n);

   return ans;

 

}

58 views
0 replies
0 upvotes

Interview problems

C++ Solution || All test case passed || Recursion and Backtracking

#include <bits/stdc++.h> 
//function to check if taking the given step is safe or not
bool isSafe (int x, int y, vector<vector<int>>& visited, vector<vector<int>>& maze, int n) {

    if ((x >= 0 && x < n) && (y >= 0 && y < n) && visited[y][x] == 0 && maze[y][x] == 1) {
        return true;
    }

    else return false;
}

//function to convert an matrix to array
vector<int> loadToArray (vector<vector<int>>& matrix) {

    vector<int> ans;

    for (int i = 0; i < matrix.size(); i++) {
        for (int j = 0; j < matrix[i].size(); j++) {
            ans.push_back(matrix[i][j]);
        }
    }

    return ans;
}

//function to solve the question using recursion
void solve (int x, int y, vector<vector<int>> visited, vector<vector<int>>& maze, vector<vector<int>>& ans, int n) {
    
    visited[y][x] = 1;

    //base case
    if (x == n-1 && y == n-1) {
        
        vector<int> temp = loadToArray(visited);
        ans.push_back(temp);

        return;
    }

    int newX, newY;

    //down
    newX = x, newY = y + 1;
    if (isSafe(newX, newY, visited, maze, n)) {
        solve(newX, newY, visited, maze, ans, n);
    }

    //left
    newX = x-1, newY = y;
    if (isSafe(newX, newY, visited, maze, n)) {
        solve(newX, newY, visited, maze, ans, n);
    }

    //up
    newX = x, newY = y-1;
    if (isSafe(newX, newY, visited, maze, n)) {
        solve(newX, newY, visited, maze, ans, n);
    }

    //right
    newX = x+1, newY = y;
    if (isSafe(newX, newY, visited, maze, n)) {
        solve(newX, newY, visited, maze, ans, n);
    }

    visited[y][x] = 0;

    return;
}

vector<vector<int>> ratInAMaze(vector<vector<int>>& maze, int n){
    vector<vector<int>> ans;
    //case
    if (maze[0][0]  == 0) return ans;

    vector<vector<int>> visited(n, vector<int>(n, 0));
    visited[0][0] = 1;

    solve(0, 0, visited, maze, ans, n);

    return ans;
}
293 views
0 replies
1 upvote

Interview problems

Simple Solution

#include <bits/stdc++.h>

void solve(int row, int col, vector<vector<int>> traverse,

vector<vector<int>> maze, int n, vector<vector<int>> &ans) {

 

if (row == n - 1 && col == n - 1) {

traverse[row][col] = 1;

 

vector<int> output;

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

output.push_back(traverse[i][j]);

}

}

ans.push_back(output);

 

return;

}

 

if (row < 0 || col < 0 || row >= n || col >= n || traverse[row][col] == 1 ||

maze[row][col] == 0) {

return;

}

 

traverse[row][col] = 1;

solve(row - 1, col, traverse, maze, n, ans);

solve(row + 1, col, traverse, maze, n, ans);

solve(row, col - 1, traverse, maze, n, ans);

solve(row, col + 1, traverse, maze, n, ans);

}

 

vector<vector<int>> ratInAMaze(vector<vector<int>> &maze, int n) {

// Write your code here.

vector<vector<int>> ans;

vector<vector<int>> traverse;

for (int i = 0; i < n; i++) {

vector<int> output;

for (int j = 0; j < n; j++) {

output.push_back(0);

}

traverse.push_back(output);

}

 

solve(0, 0, traverse, maze, n, ans);

return ans;

}

104 views
0 replies
0 upvotes

Interview problems

what's the problem with this code i am not getting output?

#include <bits/stdc++.h>

bool isPossible_to_move(int x, int y, int n,vector<vector<int>>&maze, vector<vector<int>>&map){

  if(x<=n-1 && y<=n-1 && map[x][y]==0 && maze[x][y]==1){

    return true;

  }

  return false;

}

void solve(vector<vector<int>>&maze,int n, vector<vector<int>>&ans, vector<vector<int>>&map,int x, int y,vector<int>&output){

  //base case

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

    ans.push_back(output);

    return;

  }

 

  map[x][y]=1;

  // //map to check visited or unvisited

  // for(int i=0; i<n;i++){

  //   for(int j=0;j<n;j++){

  //     map[i][j]=0;

  //   }

  // }

 

  //left

  if(isPossible_to_move(x,y-1,n,maze,map)){

 

    for(int i=0; i<n;i++){

      for(int j=0; j<n; j++){

        output.push_back(map[i][j]);

      }

    }

    // output.push_back(maze[x][y])

    solve(maze,n,ans,map,x,y-1,output);

    output.pop_back();

 

  }

  //right

  if(isPossible_to_move(x,y+1,n,maze,map)){

    for(int i=0; i<n;i++){

      for(int j=0; j<n; j++){

        output.push_back(map[i][j]);

      }

    }

    

    solve(maze,n,ans,map,x,y+1,output);

    output.pop_back();

 

  }

  //up

  if(isPossible_to_move(x-1,y,n,maze,map)){

    for(int i=0; i<n;i++){

      for(int j=0; j<n; j++){

        output.push_back(map[i][j]);

      }

    }

    

    solve(maze,n,ans,map,x-1,y,output);

    output.pop_back();

 

  }

  //down

  if(isPossible_to_move(x+1,y,n,maze,map)){

    for(int i=0; i<n;i++){

      for(int j=0; j<n; j++){

        output.push_back(map[i][j]);

      }

    }

    

    solve(maze,n,ans,map,x+1,y,output);

    output.pop_back();

 

  }

 

  map[x][y]=0;

 

}

vector<vector<int> > ratInAMaze(vector<vector<int> > &maze, int n){

  // Write your code here.

  vector<vector<int>>ans;

  vector<vector<int>>map;

  vector<int>output;

  int srcx=0;

  int srcy=0;

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

    return ans;

  }

  //map to check visited or unvisited

  for(int i=0; i<n;i++){

    for(int j=0;j<n;j++){

      map[i][j]=0;

    }

  }

  solve(maze,n,ans,map,srcx,srcy,output);

  return ans;

}

68 views
1 reply
0 upvotes

Interview problems

Java Solution

import java.util.* ;

import java.io.*; 

public class Solution {

 

    public static void addToAnswer(int n, int[][] visited, ArrayList<ArrayList<Integer>> ans){

        ArrayList<Integer> temp = new ArrayList<>();

        for(int i=0 ; i<n ; i++){

            for(int j=0 ; j<n ; j++){

                temp.add(visited[i][j]);

            }

        }

        ans.add(temp);

    }

 

    public static boolean isSafe(int row, int col, int n, int[][] arr, int[][] visited){

 

        if((row>=0 && row<n) && (col>=0 && col<n) && (arr[row][col]==1 && visited[row][col]!=1)){

            return true;

        }

        return false;

    }

 

    public static void helper(int row, int col, int n, int[][] arr, int[][] visited, ArrayList<ArrayList<Integer>> ans){

        // base case

        if(row==n-1 && col==n-1){

            visited[row][col]=1;

            addToAnswer(n,visited,ans);

            visited[row][col]=0;

            return ;

        }

 

        // update visited

        visited[row][col]=1;

 

        // for D/L/R/U

 

        // for Down

        if(isSafe(row+1,col,n,arr,visited)){

            

            helper(row+1, col, n, arr, visited, ans);

        }

 

        // for Left

        if(isSafe(row, col-1, n, arr, visited)){

            helper(row, col-1, n, arr, visited, ans);

        }

 

        // for Right

        if(isSafe(row, col+1, n, arr, visited)){

            helper(row, col+1, n, arr, visited, ans);

        }

        // for Up

        if(isSafe(row-1, col, n, arr, visited)){

            helper(row-1, col, n, arr, visited, ans);

        }

 

        visited[row][col]=0;

 

    }

 

    public static ArrayList<ArrayList<Integer>> ratInAMaze(int[][] arr, int n) {

        // Write your code here.

        int[][] visited = new int[n][n];

 

        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();

 

        if(arr[0][0]==0){ // initial starting point is 0 so we cant enter into maze

            return ans;

        }

 

        int row = 0;

        int col = 0;

 

        helper(row,col,n,arr,visited,ans);

 

        return ans;

 

    }

}

 

183 views
0 replies
0 upvotes

Interview problems

BETTER THAN 99.2% ||27ms || BEST SOLUTION

#include <bits/stdc++.h>

 

bool safe(int row, int col, int n, vector<vector<int>>& maze, vector<vector<int>>& path) {

    if (row >= 0 && row < n && col >= 0 && col < n && path[row][col] == 0 && maze[row][col] == 1) {

        return true;

    }

    return false;

}

 

void getpath(int row, int col, int n, vector<vector<int>>& maze, vector<vector<int>>& ans, vector<vector<int>>& path) {

    if (row == n - 1 && col == n - 1) {

         vector<int> temp;

    path[row][col]=1;

    for(int k=0;k<n;k++)

    {

      for(int l=0;l<n;l++)

      {

        temp.push_back(path[k][l]);

      }

    }

    path[row][col]=0;

    ans.push_back(temp);

    return;

    }

    

    path[row][col] = 1;

    

    // Down

    if (safe(row + 1, col, n, maze, path)) {

        getpath(row + 1, col, n, maze, ans, path);

    }

    

    // Left

    if (safe(row, col - 1, n, maze, path)) {

        getpath(row, col - 1, n, maze, ans, path);

    }

    

    // Right

    if (safe(row, col + 1, n, maze, path)) {

        getpath(row, col + 1, n, maze, ans, path);

    }

    

    // Up

    if (safe(row - 1, col, n, maze, path)) {

        getpath(row - 1, col, n, maze, ans, path);

    }

    

    path[row][col] = 0;

}

 

vector<vector<int>> ratInAMaze(vector<vector<int>>& maze, int n) {

    vector<vector<int>> ans;

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

 

    if (maze[0][0] == 0 || maze[n - 1][n - 1] == 0) {

        return ans; 

    }

 

    getpath(0, 0, n, maze, ans, path);

    return ans;

}

 

269 views
0 replies
3 upvotes

Interview problems

Rat in Maze all Paths C++ solution

#include <bits/stdc++.h>

using namespace std;

bool isSafe(int x, int y, vector<vector<int>>& board, int n, vector<vector<int>>&vis){

  if(vis[x][y]==1) return false;

 

  if(x>=n or x<0 or y>=n or y<0) return false;

  if(board[x][y]==0 ) return false;

  return true;

}

void addAns(vector<vector<int>>& ans,vector<vector<int>>& path, int n){

  vector<int>temp;

  for(int i=0;i<n;i++){

    for(int j=0;j<n;j++){

      temp.push_back(path[i][j]);

    }

  }

 

  ans.push_back(temp);

}

void solve(vector<vector<int>>& ans,int n, vector<vector<int>>& board, int x, int y,vector<vector<int>>& path, vector<vector<int>>& vis ){

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

    addAns(ans,path, n);

    return ;

  }

  //maze[x][y]

  vis[x][y]=1;

  //checking down

  if(isSafe(x, y+1, board, n, vis)){

    path[x][y+1]=1;

    

    solve(ans, n , board,x,y+1,path, vis );

    path[x][y+1]=0;

  }

  //checking up

  if(isSafe(x, y-1, board, n, vis)){

    path[x][y-1]=1;

    

    solve(ans, n , board, x, y-1, path, vis);

    path[x][y-1]=0;

  }

  //checking right

  if(isSafe(x+1, y, board, n, vis)){

    path[x+1][y]=1;

    

    solve(ans, n , board, x+1, y, path, vis);

    path[x+1][y]=0;

  }

  //checking left

  if(isSafe(x-1, y, board, n, vis)){

    path[x-1][y]=1;

    

    solve(ans, n , board, x-1, y, path, vis);

    path[x-1][y]=0;

  }

  vis[x][y]=0;

 

}

 

vector<vector<int> > ratInAMaze(vector<vector<int> > &maze, int n){

  

  vector<vector<int>> ans;

  vector<vector<int>>vis;

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

  path[0][0]=1;

  solve(ans, n , maze,0,0,path, vis );

  return ans;

}

 

I am not able to figure out what is wrong with this code, can anyone help?

152 views
0 replies
0 upvotes

Interview problems

Rat in a maze all paths

 

import queue from sys import stdin

def ratInAMaze(maze , n):    # Initialize the 'SOLUTION' matrix by all 0s.    solution = [[0 for j in range(n)] for i in range (n)]

   # Final call to function to print the solutions.    solveMaze(maze, solution, 0, 0, n)

def solveMaze(maze, solution, x, y, n):    # Base case that we reach our destination.    if(x == n-1 and y == n-1):        solution[x][y] = 1        printSolution(solution , n)        print("")        return

   # Condition of out of boundary of the maze.    if (x > n-1 or x < 0 or y > n-1 or y < 0):        return

   """       Condition for 'MAZE[x][y]==0' - if that particular cell is block.       'SOLUTION[x][y]'' == 1 - if it is already visited or already we go through it.    """    if(x > n-1 or x < 0 or y > n-1 or y < 0 or maze[x][y] == 0 or solution[x][y] == 1):        return    solution[x][y] = 1.    solveMaze(maze, solution, x - 1, y , n)      solveMaze(maze, solution, x + 1, y , n)     solveMaze(maze, solution, x , y - 1 , n)     solveMaze(maze, solution, x, y + 1 , n)    solution[x][y] = 0 def printSolution(solution , n):    for i in range(0 , n):        for j in range(0 , n):            print(solution[i][j] , end = " ") n = int(input()) maze = n*[0]

for i in range(0 , n):    maze[i]=input().split()    maze[i]=[int(j) for j in maze[i]]     ratInAMaze(maze , n)                                   

python

134 views
0 replies
2 upvotes
Full screen
Console