# Maximum points from top left to bottom right of Matrix

Given: Matrix of size MxN, consists of ‘#’, ‘.’ and ‘*’, where:

• # means blocked path
• . means walkable path
• * means points to collect.

Problem: To find the maximum points you can grab to reach bottom right of the matrix from top left.

Consider you are at the top left of the matrix, you have to reach the bottom right of the matrix and come back to the top left. When you are moving top left to bottom right you are allowed to walk right or down. When you are moving the bottom right to top left you are allowed to walk left or up. Points once taken will be converted into ‘.’ i.e. walkable path.

Examples:

```Input : N = 3, M = 4
****
.##.
.##.
****
Output : 8

Input : N = 9, M = 7
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........
Output : 7```

### Solution in C++:

```#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;

// Calculating the points at a (row1, col1) &&
// (row2, col2) from path1 && path2
int cost(char grid[][M], int row1, int col1,
int row2, int col2)
{
// If both path is at same cell
if (row1 == row2 && col1 == col2) {

// If the cell contain *, return 1
if (grid[row1][col1] == '*')
return 1;

// else return 0.
return 0;
}

int ans = 0;

if (grid[row1][col1] == '*')
ans++;

if (grid[row2][col2] == '*')
ans++;

return ans;
}

// Calculate the maximum points that can be
// collected.
int solve(int n, int m, char grid[][M],
int dp[MAX][MAX][MAX], int row1,
int col1, int row2)
{
int col2 = (row1 + col1) - (row2);

// If both path reach the bottom right cell
if (row1 == n - 1 && col1 == m - 1 &&
row2 == n - 1 && col2 == m - 1)
return 0;

// If moving out of grid
if (row1 >= n || col1 >= m ||
row2 >= n || col2 >= m)
return -1 * inf;

// If already calculated, return the value
if (dp[row1][col1][row2] != -1)
return dp[row1][col1][row2];

// Variable for 4 options.
int ch1 = -1 * inf, ch2 = -1 * inf;
int ch3 = -1 * inf, ch4 = -1 * inf;

// If path 1 is moving right and path 2
// is moving down.
if (grid[row1][col1 + 1] != '#' &&
grid[row2 + 1][col2] != '#')
ch1 = cost(grid, row1, col1 + 1, row2 + 1, col2) +
solve(n, m, grid, dp, row1, col1 + 1, row2 + 1);

// If path 1 is moving right and path 2 is moving
// right.
if (grid[row1][col1 + 1] != '#' &&
grid[row2][col2 + 1] != '#')
ch2 = cost(grid, row1, col1 + 1, row2, col2 + 1) +
solve(n, m, grid, dp, row1, col1 + 1, row2);

// If path 1 is moving down and path 2 is moving right.
if (grid[row1 + 1][col1] != '#' &&
grid[row2][col2 + 1] != '#')
ch3 = cost(grid, row1 + 1, col1, row2, col2 + 1) +
solve(n, m, grid, dp, row1 + 1, col1, row2);

// If path 1 is moving down and path 2 is moving down.
if (grid[row1 + 1][col1] != '#' &&
grid[row2 + 1][col2] != '#')
ch4 = cost(grid, row1 + 1, col1, row2 + 1, col2) +
solve(n, m, grid, dp, row1 + 1, col1, row2 + 1);

// Returning the maximum of 4 options.
return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}

// Wrapper Function
int wrapper(int n, int m, char grid[N][M])
{
int ans = 0;
int dp[MAX][MAX][MAX];
memset(dp, -1, sizeof dp);

// If last bottom right cell is blcoked
if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
ans = -1 * inf;

// If top left cell contain *
if (grid[0][0] == '*')
ans++;
grid[0][0] = '.';

// If bottom right cell contain *
if (grid[n - 1][m - 1] == '*')
ans++;
grid[n - 1][m - 1] = '.';

ans += solve(n, m, grid, dp, 0, 0, 0);
return max(ans, 0);
}

// Driven Program
int main()
{
int n = 5, m = 5;

char grid[N][M] = {
{ '.', '*', '.', '*', '.' },
{ '*', '#', '#', '#', '.' },
{ '*', '.', '*', '.', '*' },
{ '.', '#', '#', '#', '*' },
{ '.', '*', '.', '*', '.' }
};

cout << wrapper(n, m, grid) << endl;
return 0;
}```

Output:

```8
```

Time Complexity: O(N^3)