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 path 1 contain *, add to answer. if (grid[row1][col1] == '*') ans++; // If path contain *, add to answer. 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)