Rat Maze With Multiple Jumps Geeks For Geeks
Problem:
https://practice.geeksforgeeks.org/problems/rat-maze-with-multiple-jumps3852/1#
(It is also the problem of the day for 02-06-2022)
Solution:
class Solution
{
public int[][] ShortestDistance(int[][] matrix)
{
int[][] t=new int[matrix.length][matrix[0].length];
for(int i=0;i<matrix.length;i++){
for(int j=0;j<matrix[0].length;j++){
t[i][j]=0;
}
}
if(check(matrix,t,0,0)==true){
return t;
}
else{
int a[][]=new int[1][1];
for(int i=0;i<1;i++){
for(int j=0;j<1;j++){
a[i][j]=-1;
}
}
return a;
}
}
public static boolean boundary(int i, int j, int[][] matrix){
if(i>=matrix.length || j>=matrix[0].length || matrix[i][j]==0){
return false;
}
return true;
}
public static boolean check(int[][] matrix, int[][] t, int i, int j){
if(i==matrix.length-1 && j==matrix[0].length-1){
t[i][j]=1;
return true;
}
if(boundary(i,j,matrix)){
t[i][j]=1;
for(int steps=1;steps<=matrix[i][j];steps++){
if(check(matrix,t,i,j+steps)==true){
return true;
}
if(check(matrix,t,i+steps,j)==true){
return true;
}
}
t[i][j]=0;
}
return false;
}
}
Time Complexity: O(N*M*K)[K is the max of matrix][GFG Time:0.65/1.78]
Space Complexity: O(N*M)
Auxiliary Space: O(N*M)
Approach Used:
We will create an addition matrix t of sizes n and m and initialize it with 0. (Here 0 means default value as in the worst case of no path exists, if the path exists we will later modify it to 1).
We need to start from (0,0) and reach till (n-1,m-1).
While traversal we will see whether the cell is a non-zero value or zero value.
If it is a non-zero value then it means that many jumps the rat have to make and if it is 0 then it means the rat cannot move to that region as it is dead.
Moreover while moving we can navigate in two directions only ie either right or down.
More priority is given to the right or forward direction.
Now we will have several functions
1. boundary(): this function will check whether while traversing rat crosses the boundary or not.
2. check(): The Major function in which we will see whether the cells are non-zero or zero.
If the cells are non-zero then we will apply the loop and check for each step. Checking will be done first in the right direction and then in the down direction.
The base condition will be if the coordinates are equal to the last coordinates of the matrix. If we reach this stage it means the path is possible and we will make the value of the last coordinate as 1.
Inside the check function:
1. Check if the coordinates are pointing to the last cell or not. (Base Condition)
2. Check whether the coordinates are inside the matrix or pointing to the outer index.
3. Now make the value of cell (i,j) as 1.
Now traverse to the number of steps and in each iteration see whether we can move in the right direction or in the downwards direction by j+steps and i+steps.
If both functions return false then it means no possible value of moving in forward and downward direction, so again make the value of t[i][j] as 0.
return false.
Apply this till we reach the base condition.
Once we reached the base condition we are having out matrix t.
Now we will return t.
And if no path exists then in the main function only we will return -1.
Time Complexity is O(N*M*K) because
1. We will traverse the array due to which O(M*N) will be there
2. And while traversing if we see whether a cell has a non-zero value we will go to the right side or downside, due to this we will have additional O(K)[max of matrix]. As the maximum number of times, the rat will jump.
Total Test Cases:200
"Thanks For Reading.😇"
"Share Further To Increase Knowledge Treasure.😊"
Comments
Post a Comment