Collect Maximum Coins in Matrix

Moderate
0/80
profile
Contributed by
0 upvote
Asked in companies
OracleAdobeDunzo

Problem statement

You are given a matrix of ‘M’ rows and ‘N’ columns. The cells of the matrix contain either a coin or are empty.

You are allowed to visit every boundary cell that has a coin in it and collects that coin apart from that, you are allowed to collect the coin in one of the four adjacent cells. Find the maximum number of coins that you can collect from the matrix.

For Example : 
If Matrix of size 3 * 5 is: 
0 1 1 0 0
0 1 0 1 0
1 0 0 0 0


Then, out of the five coins in the matrix, you can collect a maximum of four coins. This is because the coin at (0, 1) lies on the boundary and after collecting the coin one can also collect the coin at (1, 1) as it lies in the adjacent cell. We can also collect the coin at (2, 0). But we cannot collect the coin at (1, 3), as this coin doesn’t lie on the boundary and it cannot be reached from one of the boundary coins.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ denoting the number of test cases, then each test case follows:

The first line of each test case contains two integers ‘M’ and ‘N’ denoting the number of rows and columns of the matrix.

The next M lines each contain N integers denoting the number of coins corresponding to each cell of the current row.
Output Format : 
For each test case, print the maximum number of coins that we can collect.

Output for each test case will be printed in a separate line.
Note : 
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints : 
1 ≤ T ≤ 10      
1 ≤ M, N ≤ 200
Matrix[i][j] = {0, 1}

Time limit: 1 sec
Sample Input 1 :
2
3 5
0 1 1 0 0
0 1 0 1 0
1 0 0 0 0
4 5
0 0 1 0 0
0 1 1 1 0
0 1 1 1 0
0 0 0 0 0
Sample Output 1 :
4
7
Explanation For Sample Input 1 :
For test case 1 :
We will print 4 because:
Out of the five coins in the matrix, you can collect a maximum of four coins. This is because the coin at (0, 1) lies on the boundary and after collecting the coin one can also collect the coin at (1, 1) as it lies in the adjacent cell of (0, 1). We can also collect the coin at (2, 0). But we cannot collect the coin at (1, 3), as this coin doesn’t lie on the boundary and it cannot be reached from one of the boundary coins.

For test case 2 : 
We will print 7 because:
Out of the seven coins in the matrix, we can collect all the seven coins using the boundary coin at (0, 2) we can directly/indirectly reach all the coins at the centre that do not directly lie on the boundary.
Sample Input 2 :
2
1 1
0
1 5
1 1 1 1 1
Sample Output 2 :
0
5
Hint

Apply depth-first search from all the boundary cells that contain a coin. 

Approaches (1)
Depth First Search

Iterate all the boundary cells and apply depth-first search from the boundary cells that contain a coin so that we can collect all the adjacent coins that don’t lie on the boundary. To apply depth-first search without using extra memory mark the cells that you have already visited as 0 (contains zero coins now) in the original matrix, this way you won’t have to maintain an extra matrix to store the visited cells. Additionally, increment the number of coins collected whenever you visit a cell that earlier had a coin but now is marked as zero.

 

The steps are as follows :

  1. Initialize the value for the variable ‘coins’ equal to zero, this variable will store the count of coins collected.
  2. Run a FOR loop to iterate all the boundary cells in the first and the last row, for each cell containing a coin, call the ‘dfs’ function from that cell.
  3. Similarly run a FOR loop to iterate all the boundary cells in the first and the last column, and call the ‘dfs’ function if the cell contains a coin.
  4. In the ‘dfs’ function, we mark the current cell equal to 0 and increment the value of ‘coins’ by 1 and then make ‘dfs’ calls to visit all the four adjacent cells of the current cell. Return the ‘dfs’ call if the current cell is doesn’t lie in the matrix or if the cell value is not equal to 1.
  5. Finally, return the value of ‘coins’.
Time Complexity

O( M * N ), where M and N denote the number of rows and columns respectively.

 

In the worst case, when all the cells contain a coin, we will end up visiting each cell exactly once using the depth-first search. The number of cells in the matrix are equal to M*N.

Hence the time complexity is O( M*N ).

Space Complexity

O( 1 )

 

No extra space is used.

Hence the space complexity is O( 1 ).

Code Solution
(100% EXP penalty)
Collect Maximum Coins in Matrix
Full screen
Console