Problem title
Difficulty
Avg time to solve

Cubic Square
Moderate
25 mins
Largest Zigzag Sequence
Moderate
20 mins
Maximum Profit
Moderate
15 mins
Consecutive Days
Moderate
10 mins
Minimum Time To Visit All Points
Moderate
15 mins
Collecting Numbers II
Moderate
30 mins
The Hero Test-2
Moderate
30 mins
Alex And Infinity Circle
Easy
15 mins
Maximise Dot Product
Hard
45 mins
Carnival With Friends
Hard
45 mins

# Collect Maximum Coins in Matrix

Difficulty: MEDIUM
Contributed By

Problem Statement

#### 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
``````
Console