NINJA’S MASTER

Easy
0/40
Average time to solve is 20m
profile
Contributed by
2 upvotes
Asked in company
Flipkart limited

Problem statement

Ninja is assigned a task to reach a target by his master. His master is taking a trial of ninja for checking how well he can listen to his commands. He left ninja in a hidden grid where each cell can be empty or blocked. Ninja has to go to the target cell from his current location in a minimum number of steps.

So your task is to find the ninja’s minimum distance to the target cell you were being provided with the starting point of the ninja.

Note: 
1. There is exactly one -1 and 2 in the grid. Remember that you will not have this information in your code.
Detailed explanation ( Input/output format, Notes, Images )
Input format: 
The first line of input contains an integer ‘T’ which denotes the number of test cases. Then, the ‘T’ test cases follow.

Each test case’s first line contains two space-separated integers, ‘n’ and ‘m’, denoting the number of rows and columns in the ‘grid’.
The next ‘n’ lines contain ‘m’ characters denoting the elements of the matrix.

grid[i][j] == -1 indicates that the ninja is in cell (i, j).
grid[i][j] == 0 indicates that the cell (i, j) is blocked.
grid[i][j] == 1 indicates that the cell (i, j) is empty.
grid[i][j] == 2 indicates that the cell (i, j) is the target cell.
Output format: 
For every test case, print the length of the shortest path to the ninja target. If no such path is available, print -1.
Note: 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 10
1 <= N, M <= 10^2
Value in each element of ‘grid’ = {‘-1’, ‘1’, ‘0’, ‘2’}

Where ‘T’ is the number of test cases, ‘N’ is the number of rows, and ‘M’ is the number of columns in a ‘grid’.

Time Limit: 1 sec

Sample Input 1:

1
3 3
0 -1 1
0 0 1
0 1 2

Sample Output 1:

3

Explanation For Sample Input 1:

Test Case 1:

Example

As you can see in the input matrix first ninja has to move right then down and then again down for reaching the destination. So the minimum steps needed are is ‘3’.

Sample Input 2:

1
3 4
0 -1 1 0
0 0 1 1
0 1 0 2

Sample Output 2:

4

Explanation For Sample Input 2:

Test Case 1:

Example

As you can see in the input matrix first ninja has to move right then down and then right and then down for reaching the destination. So the minimum steps needed are is ‘4’.
Hint

Try to iterate through all the nodes.

Approaches (2)
DFS

Approach: The idea here is to think of a matrix-like graph and do the dfs traversal and by traversing each possible path compare the value to look for the minimum value. 

 

Algorithm:

  1. Firstly we declare a  2-D array ‘VISITED’ for storing whether we have visited that particular node or not from some particular node.
  2. Now we iterate through the ‘GRID’ and find the position in the grid where it is equal to ‘-1’ or we can say starting point into the variable named as ‘X’ and ‘Y’.
  3. Now we start checking if at that point value of the grid is equal to ‘1’ or ‘2’ we called our function DFS recursively for that point.
  4. If we reached the node with value ‘2’ we compare the minimum value of ‘COUNT’ and ans and then return back from recursion.
  5. In this way, we recursively call our DFS for all the direction from one point, and thus after all the recursive calls we simply return our answer.
Time Complexity

O(N * M), where ‘N’ is the number of rows and ‘M’is the number of columns

 

As in the worst case, we have to travel our whole grid, and also in finding the starting position of ninja takes O(N * M) time.

Space Complexity

O(N * M), where ‘N’ is the number of rows and ‘M’ is the number of columns.

 

As we are using a visited array and recursion stack.

Code Solution
(100% EXP penalty)
NINJA’S MASTER
Full screen
Console