Ninja visits his friend

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote
Asked in company
Samsung

Problem statement

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’.
Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

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

Sample Output 1:

3
4

Explanation of Sample Input 1:

Test Case 1 :  
We can remove obstacle at (1,3) (1 - based indexing) and then move on shortest path in 3 steps i.e
(1,1) -> ( 1,2) -> (1,3) -> (2,3).

Test Case 2 : 
We can remove obstacle at (1,2) (1 - based indexing)  and then move like shown below in 4 steps.
(1,1) -> ( 1,2) -> (1,3) -> (2,3) -> (3,3).

Sample Input 2:

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

Sample Output 2:

2
-1
Hint

Try to use the BFS traversal.

Approaches (1)
Implementation with BFS

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.
Time Complexity

O(N * M * K), where ‘N’ and ‘M’ are rows and columns of the grid and ‘K’ is the maximum obstacle that ninja can remove.

 

In the worst case scenario, we have to put every cell in the queue ‘K’ times, making the overall complexity as O(N * M * K).

Space Complexity

O(N * M * K), where ‘N’ and ‘M’ are rows and columns of the grid and ‘K’ is the maximum obstacle that ninja can remove.

 

In the worst case, for every cell ( M * N ), we have to put that cell into the queue K times which means we need to store all of those steps/paths in the visited set.

Code Solution
(100% EXP penalty)
Ninja visits his friend
Full screen
Console