Rat in a Maze Problem when movement in all possible directions is allowed
Consider a rat placed at (0, 0) in a square matrix m[ ][ ] of order n and has to reach the destination at (n-1, n-1). The task is to find a sorted array of strings denoting all the possible directions which the rat can take to reach the destination at (n-1, n-1). The directions in which the rat can move are ‘U'(up), ‘D'(down), ‘L’ (left), ‘R’ (right).
Examples:
Input : N = 4
1 0 0 0
1 1 0 1
0 1 0 0
0 1 1 1
Output :
DRDDRRInput :N = 4
1 0 0 0
1 1 0 1
1 1 0 0
0 1 1 1
Output :
DDRDRR DRDDRR
Explanation:
Solution:
Brute Force Approach:
We can use simple backtracking without using any extra space .
C++
// C++ implementation of the above approach #include <bits/stdc++.h> #define MAX 5 using namespace std; void getallpath( int matrix[MAX][MAX], int n, int row, int col,vector<string> &ans,string cur) { if (row>=n or col>=n or row<0 or col<0 or matrix[row][col] == 0) return ; if (row == n-1 and col == n-1) { ans.push_back(cur); return ; } //now if its one we have 4 calls matrix[row][col] = 0; getallpath(matrix,n,row-1,col,ans,cur+ "U" ); getallpath(matrix,n,row,col+1,ans,cur+ "R" ); getallpath(matrix,n,row,col-1,ans,cur+ "L" ); getallpath(matrix,n,row+1,col,ans,cur+ "D" ); matrix[row][col] = 1; return ; } vector<string> findPath( int matrix[MAX][MAX], int n) { // Your code goes here vector<string> ans; getallpath(matrix,n,0,0,ans, "" ); return ans; } int main() { int m[MAX][MAX] = { { 1, 0, 0, 0, 0 }, { 1, 1, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 1 } }; int n = sizeof (m) / sizeof (m[0]); vector<string> ans = findPath(m, n); for ( auto i : ans) cout<<i<< " " ; return 0; } |
Java
import java.util.*; public class Main { static final int MAX = 5 ; static void getallpath( int [][] matrix, int n, int row, int col, List<String> ans, String cur) { if (row >= n || col >= n || row < 0 || col < 0 || matrix[row][col] == 0 ) { return ; } if (row == n - 1 && col == n - 1 ) { ans.add(cur); return ; } matrix[row][col] = 0 ; getallpath(matrix, n, row - 1 , col, ans, cur + "U" ); getallpath(matrix, n, row, col + 1 , ans, cur + "R" ); getallpath(matrix, n, row, col - 1 , ans, cur + "L" ); getallpath(matrix, n, row + 1 , col, ans, cur + "D" ); matrix[row][col] = 1 ; return ; } static List<String> findPath( int [][] matrix, int n) { List<String> ans = new ArrayList<>(); getallpath(matrix, n, 0 , 0 , ans, "" ); return ans; } public static void main(String[] args) { int [][] m = { { 1 , 0 , 0 , 0 , 0 }, { 1 , 1 , 1 , 1 , 1 }, { 1 , 1 , 1 , 0 , 1 }, { 0 , 0 , 0 , 0 , 1 }, { 0 , 0 , 0 , 0 , 1 } }; int n = m.length; List<String> ans = findPath(m, n); for (String i : ans) { System.out.println(i + " " ); } } } // This code is contributed by abn95knd1. |
Python3
# Python3 implementation of the above approach def getallpath(m, n, ans, curpath, r, c): if (r> = n or c> = n or r< 0 or c< 0 or m[r] = = 0 ): return ; if (r = = n - 1 and c = = n - 1 ): ans.append(curpath) return m[r] = 0 # calls getallpath(m,n,ans,curpath + "U" ,r - 1 ,c) getallpath(m,n,ans,curpath + "D" ,r + 1 ,c) getallpath(m,n,ans,curpath + "L" ,r,c - 1 ) getallpath(m,n,ans,curpath + "R" ,r,c + 1 ) m[r] = 1 ; # Function to store and print # all the valid paths def findpath(m ,n): # vector to store all the possible paths possiblePaths = [] getallpath(m,n,possiblePaths,"", 0 , 0 ) # Print all possible paths for i in range ( len (possiblePaths)): print (possiblePaths[i], end = " " ) # Driver code if __name__ = = "__main__" : m = [ [ 1 , 0 , 0 , 0 , 0 ], [ 1 , 1 , 1 , 1 , 1 ], [ 1 , 1 , 1 , 0 , 1 ], [ 0 , 0 , 0 , 0 , 1 ], [ 0 , 0 , 0 , 0 , 1 ] ] n = len (m) findpath(m, n) # This code is contributed by Arpit Jain |
C#
using System; using System.Collections.Generic; namespace Algorithm { class MainClass { static readonly int MAX = 5; static void getallpath( int [,] matrix, int n, int row, int col, List< string > ans, string cur) { if (row >= n || col >= n || row < 0 || col < 0 || matrix[row, col] == 0) { return ; } if (row == n - 1 && col == n - 1) { ans.Add(cur); return ; } matrix[row, col] = 0; getallpath(matrix, n, row - 1, col, ans, cur + "U" ); getallpath(matrix, n, row, col + 1, ans, cur + "R" ); getallpath(matrix, n, row, col - 1, ans, cur + "L" ); getallpath(matrix, n, row + 1, col, ans, cur + "D" ); matrix[row, col] = 1; return ; } static List< string > findPath( int [,] matrix, int n) { List< string > ans = new List< string >(); getallpath(matrix, n, 0, 0, ans, "" ); return ans; } public static void Main( string [] args) { int [,] m = { { 1, 0, 0, 0, 0 }, { 1, 1, 1, 1, 1 }, { 1, 1, 1, 0, 1 }, { 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 1 } }; int n = m.GetLength(0); List< string > ans = findPath(m, n); foreach ( string i in ans) { Console.Write(i + " " ); } } } } |
Javascript
// The equivalent JavaScript code is as follows: const MAX = 5; function getallpath(matrix, n, row, col, ans, cur) { if (row >= n || col >= n || row < 0 || col < 0 || matrix[row][col] === 0) { return ; } if (row === n - 1 && col === n - 1) { ans.push(cur); return ; } matrix[row][col] = 0; getallpath(matrix, n, row - 1, col, ans, cur + "U" ); getallpath(matrix, n, row, col + 1, ans, cur + "R" ); getallpath(matrix, n, row, col - 1, ans, cur + "L" ); getallpath(matrix, n, row + 1, col, ans, cur + "D" ); matrix[row][col] = 1; return ; } function findPath(matrix, n) { let ans = []; getallpath(matrix, n, 0, 0, ans, "" ); return ans; } let m = [ [1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 1, 0, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 1], ]; let n = m.length; let ans = findPath(m, n); for (let i of ans) { console.log(i + " " ); } |
DRRRRDDD DRDRURRDDD DDRURRRDDD DDRRURRDDD
Complexity Analysis:
Time Complexity: O(3^(n^2))
As we are making 4 calls for every cell in the matrix.
Auxiliary Space: O(1)
As we are not using any extra space.
Contact Us