Last Updated: 29 Oct, 2021
Collect Maximum Coins in Matrix
Moderate
Asked in companies
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.
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
Approaches
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 :
- Initialize the value for the variable ‘coins’ equal to zero, this variable will store the count of coins collected.
- 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.
- 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.
- 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.
- Finally, return the value of ‘coins’.