Last Updated: 7 Apr, 2021
NINJA’S MASTER
Easy
Asked in company
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
Approaches
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:
- Firstly we declare a 2-D array ‘VISITED’ for storing whether we have visited that particular node or not from some particular node.
- 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’.
- 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.
- If we reached the node with value ‘2’ we compare the minimum value of ‘COUNT’ and ans and then return back from recursion.
- 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.
Approach: The idea here is to think of a matrix-like graph and do the bfs traversal. We use recursion for this and try to find out the minimum by calling our function for the next path.
Algorithm:
- Firstly we declare a queue that can store pairs of integers and uses a visited array for storing the information whether we have visited that node from that particular point.
- 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’.
- Now we start pushing our node into that if the node has value ‘1’ or ‘2’.
- In one traversal of the queue, we increase the count by 1 as in one traversal we can visit that four nodes at a time.
- If we reached the node with value ‘2’ we simply return the ‘COUNT’ as this is the minimum value as we are traversing in all possible directions the node which we reached the first is the best possible count.
- So we returned our final answer.