এই টিউটোরিয়ালে, আমরা ম্যাট্রিক্সের উপরের বাম থেকে নীচের ডানদিকে সর্বাধিক পয়েন্ট খুঁজে বের করতে এবং ফিরে আসার জন্য একটি প্রোগ্রাম নিয়ে আলোচনা করব
এর জন্য আমাদেরকে #-অবরুদ্ধ পথ, *-পয়েন্ট, .- অনুমোদিত পথ সমন্বিত ম্যাট্রিক্স সরবরাহ করা হবে। আমাদের কাজ হল এক কোণ থেকে অন্য কোণে যাওয়া (ডান এবং নীচের মুভ) এবং ফিরে আসা (বাম এবং উপরের চাল) যেমন সর্বাধিক পয়েন্ট সংগ্রহ করা
উদাহরণ
#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
