इस ट्यूटोरियल में, हम मैट्रिक्स के ऊपर बाईं ओर से नीचे दाईं ओर अधिकतम अंक खोजने और वापस लौटने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें #-blocked पथ, *-points, .- अनुमत पथ से युक्त मैट्रिक्स प्रदान किया जाएगा। हमारा काम एक कोने से दूसरे कोने में जाना है (दाएं और नीचे की चाल) और वापस आना (बाएं और ऊपर की चाल) जैसे कि अधिकतम अंक एकत्र करना
उदाहरण
#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;
} आउटपुट
8