Last Updated: 28 Mar, 2021
Ninja visits his friend
Moderate
Asked in company
Ninja and his friend live in a grid of size ‘N x M’, with rows numbered 1 to ‘N’ from top to bottom, and columns numbered 1 to ‘M’ from left to right. Ninja lives in the top-left cell and his friend lives in the bottom-right cell.
Every cell is either allowed or blocked by an obstacle.
Ninja wants your help to find the minimum path from his home to his friend given that Ninja can use a secret technique that can remove at most ‘K’ obstacles.
Note:
If Ninja is unable to reach his friend’s house then return -1.
Empty cell in the matrix is represented by ‘0’ and an obstacle by ‘1’.
Input Format
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains three space-separated integers, 'N' and 'M', denoting the number of rows and columns in the matrix 'MAT', respectively and ‘K’, denoting the atmost numbers of obstacles Ninja can remove.
Each of the next 'N' lines contains 'M' space-separated integers denoting the matrix 'MAT' elements.
Output Format:
For each test case, print a single line containing a single integer denoting the minimum number of steps needed to reach Ninja’s friend's house from Ninja house.
The output of each test case will be printed in a separate line.
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 <= 50
1<= K <= N * M
0 <= MAT[ i ][ j ] <= 1
Where 'T' denotes the number of test cases, 'N' and 'M' denotes the number of rows and columns in the matrix 'MAT' respectively, 'K' denotes the most numbers of obstacles Ninja can remove and 'MAT[i][j]' denotes the element present at the 'i'th' row and the 'j'th' column of the matrix 'MAT'.
Time limit: 1 sec.
Approaches
The idea here is that we will use simple BFS(breadth first search) but with extra conditions that we can only move to the next cell when ‘k’ value is greater than 0.
We need to store the values of already used k i.e. ninja's secret technique.
We create a queue that can store 4 things i.e position, steps and k used.
Algorithm:
- Declare a 2d array ‘vis’ of size n x m with initial value -1 and a queue of array.
- Push {0,0,0,k} in the queue which denotes x, y, steps and technique left resp.
- While q is not empty or we visited the last cell we keep on searching
- Check for the connected cell by adding (1,0), (0,1), (-1,0), (0,-1) to the current cell
- If the cell does exist in the grid and has some k value left then push to queue else continue.
- If the x = n-1 and y = m-1 then return the current Steps.
- return -1 this means we are unable to reach the last cell.