Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Problem of the day

You are given a two-dimensional matrix of integers of dimensions N*M, where each cell represents the number of coins in that cell. Alice and Bob have to collect the maximum number of coins. The followings are the conditions to collect coins:

Alice starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (N-1, 0). Bob starts from top right corner, i.e., (0, M-1) and should reach bottom right corner, i.e., (N-1, M-1).

From a point (i, j), Alice and Bob can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

They have to collect all the coins that are present at a cell. If Alice has already collected coins of a cell, then Bob gets no coins if goes through that cell again.

```
If the matrix is
0 2 4 1
4 8 3 7
2 3 6 2
9 7 8 3
1 5 9 4
Then answer is 47. As, Alice will collect coins 0+8+3+9+1 = 21 coins. Bob will collect coins 1+7+6+8+4 = 26 coins. Total coins is 21+26 = 47 coins.
```

Detailed explanation

```
1 <= T <= 5
1 <= N <= 10^2
1 <= M <= 10^2
0 <= MAT[i][j] <= 10^3
Time Limit: 1 sec
```

```
1
5 4
3 6 8 2
5 2 4 3
1 1 20 10
1 1 20 10
1 1 20 10
```

```
73
```

```
Alice will collect coins 3 + 2 + 20 + 1 + 1 = 27 coins.
Bob will collect coins 2 + 4 + 10 + 20 + 10 = 46 coins.
So total coins will get connected are 27 + 46 = 73 coins.
```

```
1
4 1
3
6
7
8
```

```
24
```

```
As, initially both are at (0,0) so either Alice or Bob can pick up 3 coins. Similarly is the case with every coin. So total 24 coins will get picked.
```