0

Collect Maximum Coins in Matrix

Difficulty: MEDIUM
Contributed By
Anshul Garg

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.
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
Reset Code
Full screen
copy-code
Console