Maximum points from top left of matrix to bottom right and return back in C++

Question

---

In this tutorial, we will be discussing a program to find maximum points from top left of matrix to bottom right and return back

For this we will be provided with matrix consisting of #-blocked path, *-points, .- allowed path. Our task is to go from one corner to another (right and below moves) and come back (left and top moves) such as to collect maximum points

Example

 Live Demo

#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
//calculating points
int cost(char grid[][M], int row1, int col1, int row2, int col2) {
   if (row1 == row2 && col1 == col2) {
      if (grid[row1][col1] == '*')
         return 1;
      return 0;
   }
   int ans = 0;
   if (grid[row1][col1] == '*')
      ans++;
   if (grid[row2][col2] == '*')
      ans++;
   return ans;
}
//calculating maximum points
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 (row1 == n - 1 && col1 == m - 1 && row2 == n - 1 && col2 == m - 1)
      return 0;
   if (row1 >= n || col1 >= m || row2 >= n || col2 >= m)
      return -1 * inf;
   if (dp[row1][col1][row2] != -1)
      return dp[row1][col1][row2];
   int ch1 = -1 * inf, ch2 = -1 * inf;
   int ch3 = -1 * inf, ch4 = -1 * inf;
   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 (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 (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 (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);
   return dp[row1][col1][row2] = max({ch1, ch2, ch3, ch4});
}
int wrapper(int n, int m, char grid[N][M]) {
   int ans = 0;
   int dp[MAX][MAX][MAX];
   memset(dp, -1, sizeof dp);
   if (grid[n - 1][m - 1] == '#' || grid[0][0] == '#')
      ans = -1 * inf;
   if (grid[0][0] == '*')
      ans++;
   grid[0][0] = '.';
   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);
}
int main() {
   int n = 5, m = 5;
   char grid[N][M] = {
      { '.', '*', '.', '*', '.' },
      { '*', '#', '#', '#', '.' },
      { '*', '.', '*', '.', '*' },
      { '.', '#', '#', '#', '*' },
      { '.', '*', '.', '*', '.' }
   };
   cout << wrapper(n, m, grid) << endl;
   return 0;
}

Output

8

Ayush Gupta

Published on 09-Sep-2020 12:14:30