मैट्रिक्स दी गई है जिसमें '#' अवरुद्ध पथ, '*' अंक, '.' अनुमत पथ है। शीर्ष-बाएं से नीचे-दाएं जाएं (दाएं/नीचे चाल) और वापस आएं (बाएं/ऊपर चाल) ताकि अधिकतम अंक एकत्र हों।
दो पथ एक साथ सोचें: दोनों (0,0) से (n-1,m-1) तक जाते हैं। DP स्थिति: dp[row1][col1][row2]।
उदाहरण 5x5 मैट्रिक्स के लिए अधिकतम अंक 8।
C++ कार्यान्वयन
#include <bits/stdc++.h>
#define MAX 5
#define N 5
#define M 5
#define inf 100000
using namespace std;
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;
}
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 -inf;
if (dp[row1][col1][row2] != -1) return dp[row1][col1][row2];
int ch1 = -inf, ch2 = -inf, ch3 = -inf, ch4 = -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 = -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;
}
आउटपुट
8
