A variation of Rat in a Maze : multiple steps or jumps allowed
A variation of rat in a maze.
You are given an N * N 2-D matrix shaped maze (let’s call it M), there is a rat in the top-left cell i.e. M[0][0] and there is an escape door in the bottom-right cell i.e. M[N-1][N-1]. From each cell M[i][j] (0 ? i ? N-1, 0 ? j ? N-1) the rat can go a number of steps towards its right ( for eg: to M[i][j+ s]), or a number of steps downwards ( for eg: to M[i+ s][j]), where the maximum number of steps (or maximum value of s) can be the value in the cell M[i][j]. If any cell contains 0 then that is a dead-end. For eg: In the second picture in the figure below, the rat at M[0][0] can jump to a cell : M[0][1], M[0][2], M[1][0] or M[2][0].
You have to print a possible path from M[0][0] to M[N-1][N-1] in the form of a matrix of size N * N such that the cells that are in the path have a value 1 and other cells have a value 0. For the above example one such solution is :
There is a backtracking solution for this problem in this article.
Here a Dynamic Programming based solution is presented.
Examples:
Input: mat[][] = {
{3, 0, 0, 2, 1},
{0, 0, 0, 0, 2},
{0, 1, 0, 1, 0},
{1, 0, 0, 1, 1},
{3, 0, 0, 1, 1} }
Output:
1 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0 0 0 0 1
0 0 0 0 1Input: mat[][] = { {0, 0}, {0, 1} }
Output: No path exists
Approach:
- Initialize a boolean CRF[N][N] (can reach from) matrix with false. Now make CRF[N – 1][N – 1] = true as destination can be reached from the destination.
- Now, starting from maze[N – 1][N – 1] and ending at maze[0][0] update all the cells in CRF[][] according to whether it is possible to reach any other valid cell (leading to the destination).
- When all of the CRF[][] matrix has been updated, use to create a matrix which contains all 1s at the cells in the path leading to the destination and other cells are 0s.
- Print this newly created matrix in the end.
- If it is not possible to reach the destination then print No path exists.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; // Function to check whether the path exists bool hasPath(vector<vector< int >> maze, vector<vector< int >>& sol, int N) { for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) sol[i][j] = 0; // Declaring and initializing CRF // (can reach from) matrix vector<vector< bool >> CRF(N); for ( int i = 0; i < N; i++) CRF[i] = vector< bool >(N); for ( int i = 0; i < N; i++) for ( int j = 0; j < N; j++) CRF[i][j] = false ; CRF[N - 1][N - 1] = true ; // Using the DP to fill CRF matrix // in correct order for ( int k = N - 1; k >= 0; k--) { for ( int j = k; j >= 0; j--) { if (!(k == N - 1 && j == N - 1)) { // If it is possible to get // to a valid location from // cell maze[k][j] for ( int a = 0; a <= maze[k][j]; a++) { if ((j + a < N && CRF[k][j + a] == true ) || (k + a < N && CRF[k + a][j] == true )) { CRF[k][j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j][k] for ( int a = 0; a <= maze[j][k]; a++) { if ((k + a < N && CRF[j][k + a] == true ) || (j + a < N && CRF[j + a][k] == true )) { CRF[j][k] = true ; break ; } } } } } // If CRF[0][0] is false it means we cannot reach // the end of the maze at all if (CRF[0][0] == false ) return false ; // Filling the solution matrix using CRF int i = 0, j = 0; while (!(i == N - 1 && j == N - 1)) { sol[i][j] = 1; if (maze[i][j] > 0) // Get to a valid location from // the current cell for ( int a = 1; a <= maze[i][j]; a++) { if ((j + a < N && CRF[i][j + a] == true )) { j = j + a; break ; } else if ((i + a < N && CRF[i + a][j] == true )) { i = i + a; break ; } } } sol[N - 1][N - 1] = 1; return true ; } // Utility function to print the contents // of a 2-D array void printMatrix(vector<vector< int >> sol, int N) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << sol[i][j] << " " ; cout << "\n" ; } } // Driver code int main() { vector<vector< int >> maze = { { 2, 2, 1, 1, 0 }, { 0, 0, 3, 0, 0 }, { 1, 0, 0, 0, 0 }, { 0, 0, 2, 0, 1 }, { 0, 0, 3, 0, 0 } }; int N = maze.size(); vector<vector< int >> sol(N,vector< int >(N)); // If path exists if (hasPath(maze, sol, N)) // Print the path printMatrix(sol, N); else cout << "No path exists" ; return 0; } |
Java
// Java implementation of the approach class GFG { static int MAX = 50 ; // Function to check whether the path exists static boolean hasPath( int maze[][], int sol[][], int N) { for ( int i = 0 ; i < N; i++) for ( int j = 0 ; j < N; j++) sol[i][j] = 0 ; // Declaring and initializing CRF // (can reach from) matrix boolean [][]CRF = new boolean [N][N]; CRF[N - 1 ][N - 1 ] = true ; // Using the DP to fill CRF matrix // in correct order for ( int k = N - 1 ; k >= 0 ; k--) { for ( int j = k; j >= 0 ; j--) { if (!(k == N - 1 && j == N - 1 )) { // If it is possible to get // to a valid location from // cell maze[k][j] for ( int a = 0 ; a <= maze[k][j]; a++) { if ((j + a < N && CRF[k][j + a] == true ) || (k + a < N && CRF[k + a][j] == true )) { CRF[k][j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j][k] for ( int a = 0 ; a <= maze[j][k]; a++) { if ((k + a < N && CRF[j][k + a] == true ) || (j + a < N && CRF[j + a][k] == true )) { CRF[j][k] = true ; break ; } } } } } // If CRF[0][0] is false it means we cannot reach // the end of the maze at all if (CRF[ 0 ][ 0 ] == false ) return false ; // Filling the solution matrix using CRF int i = 0 , j = 0 ; while (!(i == N - 1 && j == N - 1 )) { sol[i][j] = 1 ; if (maze[i][j] > 0 ) // Get to a valid location from // the current cell for ( int a = 1 ; a <= maze[i][j]; a++) { if ((j + a < N && CRF[i][j + a] == true )) { j = j + a; break ; } else if ((i + a < N && CRF[i + a][j] == true )) { i = i + a; break ; } } } sol[N - 1 ][N - 1 ] = 1 ; return true ; } // Utility function to print the contents // of a 2-D array static void printMatrix( int sol[][], int N) { for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) System.out.print(sol[i][j] + " " ); System.out.println(); } } // Driver code public static void main(String[] args) { int maze[][] = {{ 2 , 2 , 1 , 1 , 0 }, { 0 , 0 , 3 , 0 , 0 }, { 1 , 0 , 0 , 0 , 0 }, { 0 , 0 , 2 , 0 , 1 }, { 0 , 0 , 3 , 0 , 0 }}; int N = maze.length; int [][]sol = new int [N][MAX]; // If path exists if (hasPath(maze, sol, N)) // Print the path printMatrix(sol, N); else System.out.println( "No path exists" ); } } // This code is contributed by Princi Singh |
C#
// C# implementation of the approach using System; class GFG { static int MAX = 50; // Function to check whether the path exists static Boolean hasPath( int [,]maze, int [,]sol, int N) { int i, j, k; for (i = 0; i < N; i++) for (j = 0; j < N; j++) sol[i, j] = 0; // Declaring and initializing CRF // (can reach from) matrix Boolean [,]CRF = new Boolean[N, N]; CRF[N - 1, N - 1] = true ; // Using the DP to fill CRF matrix // in correct order for (k = N - 1; k >= 0; k--) { for (j = k; j >= 0; j--) { if (!(k == N - 1 && j == N - 1)) { // If it is possible to get // to a valid location from // cell maze[k,j] for ( int a = 0; a <= maze[k, j]; a++) { if ((j + a < N && CRF[k, j + a] == true ) || (k + a < N && CRF[k + a, j] == true )) { CRF[k, j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j,k] for ( int a = 0; a <= maze[j, k]; a++) { if ((k + a < N && CRF[j, k + a] == true ) || (j + a < N && CRF[j + a, k] == true )) { CRF[j, k] = true ; break ; } } } } } // If CRF[0,0] is false it means we cannot // reach the end of the maze at all if (CRF[0, 0] == false ) return false ; // Filling the solution matrix using CRF i = 0; j = 0; while (!(i == N - 1 && j == N - 1)) { sol[i, j] = 1; if (maze[i, j] > 0) // Get to a valid location from // the current cell for ( int a = 1; a <= maze[i, j]; a++) { if ((j + a < N && CRF[i, j + a] == true )) { j = j + a; break ; } else if ((i + a < N && CRF[i + a, j] == true )) { i = i + a; break ; } } } sol[N - 1, N - 1] = 1; return true ; } // Utility function to print the contents // of a 2-D array static void printMatrix( int [,]sol, int N) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) Console.Write(sol[i, j] + " " ); Console.WriteLine(); } } // Driver code public static void Main(String[] args) { int [,]maze = {{ 2, 2, 1, 1, 0 }, { 0, 0, 3, 0, 0 }, { 1, 0, 0, 0, 0 }, { 0, 0, 2, 0, 1 }, { 0, 0, 3, 0, 0 }}; int N = maze.GetLength(0); int [,]sol = new int [N, MAX]; // If path exists if (hasPath(maze, sol, N)) // Print the path printMatrix(sol, N); else Console.WriteLine( "No path exists" ); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation of the approach var MAX = 50; // Function to check whether the path exists function hasPath(maze, sol, N) { for ( var i = 0; i < N; i++) for ( var j = 0; j < N; j++) sol[i][j] = 0; // Declaring and initializing CRF // (can reach from) matrix var CRF = Array.from(Array(N), ()=>Array(N));; for ( var i = 0; i < N; i++) for ( var j = 0; j < N; j++) CRF[i][j] = false ; CRF[N - 1][N - 1] = true ; // Using the DP to fill CRF matrix // in correct order for ( var k = N - 1; k >= 0; k--) { for ( var j = k; j >= 0; j--) { if (!(k == N - 1 && j == N - 1)) { // If it is possible to get // to a valid location from // cell maze[k][j] for ( var a = 0; a <= maze[k][j]; a++) { if ((j + a < N && CRF[k][j + a] == true ) || (k + a < N && CRF[k + a][j] == true )) { CRF[k][j] = true ; break ; } } // If it is possible to get to // a valid location from cell // maze[j][k] for ( var a = 0; a <= maze[j][k]; a++) { if ((k + a < N && CRF[j][k + a] == true ) || (j + a < N && CRF[j + a][k] == true )) { CRF[j][k] = true ; break ; } } } } } // If CRF[0][0] is false it means we cannot reach // the end of the maze at all if (CRF[0][0] == false ) return false ; // Filling the solution matrix using CRF var i = 0, j = 0; while (!(i == N - 1 && j == N - 1)) { sol[i][j] = 1; if (maze[i][j] > 0) // Get to a valid location from // the current cell for ( var a = 1; a <= maze[i][j]; a++) { if ((j + a < N && CRF[i][j + a] == true )) { j = j + a; break ; } else if ((i + a < N && CRF[i + a][j] == true )) { i = i + a; break ; } } } sol[N - 1][N - 1] = 1; return true ; } // Utility function to print the contents // of a 2-D array function printMatrix( sol, N) { for ( var i = 0; i < N; i++) { for ( var j = 0; j < N; j++) document.write( sol[i][j] + " " ); document.write( "<br>" ); } } // Driver code var maze = [ [ 2, 2, 1, 1, 0 ], [ 0, 0, 3, 0, 0 ], [ 1, 0, 0, 0, 0 ], [ 0, 0, 2, 0, 1 ], [ 0, 0, 3, 0, 0 ] ]; var N = maze.length; var sol = Array.from(Array(N), ()=>Array(MAX)); // If path exists if (hasPath(maze, sol, N)) // Print the path printMatrix(sol, N); else document.write( "No path exists" ); </script> |
Python3
# Python3 implementation of the approach MAX = 50 # Function to check whether the path exists def hasPath(maze, sol,N): for i in range (N): for j in range (N): sol[i][j] = 0 # Declaring and initializing CRF # can reach from matrix CRF = [[ False ] * N for _ in range (N)] for i in range (N): for j in range (N): CRF[i][j] = False CRF[N - 1 ][N - 1 ] = True # Using the DP to fill CRF matrix # in correct order for k in range (N - 1 , - 1 , - 1 ): for j in range (k, - 1 , - 1 ): if not (k = = N - 1 and j = = N - 1 ): # If it is possible to get # to a valid location from # cell maze[k][j] for a in range (maze[k][j] + 1 ): if (j + a < N and CRF[k][j + a]) or (k + a < N and CRF[k + a][j]): CRF[k][j] = True break # If it is possible to get to # a valid location from cell # maze[j][k] for a in range (maze[j][k] + 1 ): if ((k + a < N and CRF[j][k + a]) or (j + a < N and CRF[j + a][k])): CRF[j][k] = True break # If CRF[0][0] is false it means we cannot reach # the end of the maze at all if not CRF[ 0 ][ 0 ]: return False # Filling the solution matrix using CRF i = 0 ; j = 0 while ( not (i = = N - 1 and j = = N - 1 )): sol[i][j] = 1 if (maze[i][j] > 0 ): # Get to a valid location from # the current cell for a in range ( 1 ,maze[i][j] + 1 ): if (j + a < N and CRF[i][j + a]): j = j + a break elif ((i + a < N and CRF[i + a][j])): i = i + a break sol[N - 1 ][N - 1 ] = 1 return True # Utility function to print the contents # of a 2-D array def printMatrix(sol, N): for i in range (N): for j in range (N): print (sol[i][j],end = " " ) print () # Driver code if __name__ = = '__main__' : maze = [ [ 2 , 2 , 1 , 1 , 0 ], [ 0 , 0 , 3 , 0 , 0 ], [ 1 , 0 , 0 , 0 , 0 ], [ 0 , 0 , 2 , 0 , 1 ], [ 0 , 0 , 3 , 0 , 0 ] ] N = len (maze) sol = [[ 0 ] * N for _ in range ( MAX )] # If path exists if (hasPath(maze, sol, N)): # Print the path printMatrix(sol, N) else : print ( "No path exists" ) # This code is contributed by Amartya Ghosh |
1 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
Complexity Analysis:
- Time Complexity: O(N ^ 2 * MAX), where N is the number of rows and MAX is the maximum element in the matrix.
- Auxiliary Space: O(N * N)
Contact Us