NINJA’S MASTER

Posted: 7 Apr, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.
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
Approach 1

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.
Try Problem