Clearing the Forest

Moderate
0/80
Average time to solve is 15m
3 upvotes
Asked in companies
Flipkart limitedTower Research Capital

Problem statement

Ninja lives in a beautiful city known as Byteland. A grand festive event is going to be organised in the city. To make place for the event, King has ordered Ninja to clear the nearby forest. The forest can be represented in the form of ‘N’*‘M’ grid ‘FOREST’, where each cell of ‘FOREST’ can have one of the possible values:

0 -> The cell is empty and Ninja can pass through it.
‘X’  -> The cell contains a tree with a height equal to ‘X’ where  ‘X’ > 0 and Ninja can pass through it.
-1 -> The cell can not be visited by Ninja.

Ninja is present at the top left corner of ‘FOREST’ i.e. at cell(0,0) and he has to cut down all the trees in ‘FOREST’. In one step ninja can move to any one of the four directions: East, West, North, South.

There is a rule that Ninja must cut off the trees in order from shortest to tallest and after cutting a tree, the value of the cell will become 0.

While standing on a cell with a tree, Ninja always has a choice to cut the tree or pass through the cell. It is guaranteed that no two cells will have the same height and there will always be at least one tree that need to be cut off.

Your task is to help Ninja to cut down all trees in ‘FOREST’ with minimum steps and return the number of steps.

If there is at least one tree that can not be cut off then return -1.

For example :

If ‘FOREST’ is :
[1,2,0]
[-1,5,-1]
[0,6,7]

We can see we need 4 steps to cut down all trees as shown below:

Example

So, the output will be 4.
Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer ‘T’ denoting the number of test cases. Then each test case follows.

The first line of each test case contains two single space-separated integers ‘N’ and ‘M’ representing the number of rows and columns in ‘FOREST’. 

The next ‘N’ lines of each test case contain ‘M’ single space-separated integers denoting the values of ‘FOREST’.

Output format:

For each test case, print a single line containing a singe integer representing the minimum number of steps to cut down all the trees.

The output of every test case will be printed in a separate line.

Note :

You don’t have to print anything, it has already been taken care of. Just implement the given function.

Constraints

1 <= T <=10
1 <= N, M <= 50
-1 <= FOREST[i] <= 10 ^ 5

Where ‘T’ denotes the number of test cases, ‘N’ denotes the number of rows and ‘M’ denotes the number of columns of ‘FOREST’.

Time limit: 1 second

Sample input 1:

1
3 3
5 0 7
3 2 -1
6 -1 1

Sample output 1:

-1

Explanation for sample input 1:

The forest can be represented as:

Example

There is no way such that we can cut off all the trees in ‘FOREST’, so we will return -1.

Sample input 2:

2    
3 3
0 5 6
2 3 7
-1 -1 8
1 1
8

Sample output 2:

6
0

Explanation for sample input 2:

For test case 1:
We can see from the below image that we need 6 steps to cut off all trees.

Example

For test case 2:
The forest has only 1 tree at (0,0) and Ninja is also at (0,0), so he can cut off the tree without using any moves.
Hint

Can you think of an algorithm that helps us find the shortest path between two points?

Approaches (1)
Sort + BFS

The idea is to first find all the trees and their coordinates and then sort the trees according to their height. Then we just need to find the steps needed between two consecutive trees. We will use Breadth-First-Search algorithm to find the shortest path between two trees. 

 

Complete Algorithm:

  1. Iterate over ‘FOREST’ and find out all trees (i.e cells having value greater than 0).
  2. Save height and the coordinates of all trees in an array/list of arrays/lists say ‘TREES’ and sort the array according to heights (We can also use HashMap for this step).
  3. Make a helper function say FIND_DIST() which receives four variables that are the coordinates of starting point and ending point for which we want to find the distance between them.
  4. FIND_DIST() will use BFS to find distance between points as explained below:
    1. Let’s say (‘R1’, ’C1’) are coordinates of starting point and (‘R2, ‘C2’) are coordinates for ending point.
    2. We will use a queue to implement BFS.
    3. Intialise an integer variable ‘STEP’ = 0.
    4. Enque the starting point coordinates or we can say (‘R1’, ’C1’) .
    5. Repeat steps 6 and 7 till the queue is not empty.
    6. Increase the value of ‘STEP’ by 1.
    7. Let’s say ‘SIZE’ is the size of queue, so run a for loop ‘SIZE’ times and inside the loop do following steps:
      1. Check all the four neighbours(if possible) of current coordinates.
      2. If any of them match with (‘R2, ‘C2’) then return ‘STEP’.
      3. Enque the neighbours which are possible to pass through and are not visited till.
  5. Iterate over “TREES’ and find dist between two consecutive trees with help of FIND_DIST() function.
  6. If at any step FIND_DIST() returns -1 in the earlier step then we will also return -1. Otherwise we will return the sum of all values returned by FIND_DIST().
Time Complexity

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

 

In the worst-case scenario for all N * M trees, we iterate N * M times to find the distance.

Space Complexity

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

 

This is the space used to store coordinates of all N * M trees.

Code Solution
(100% EXP penalty)
Clearing the Forest
Full screen
Console