Maximum points from top left of matrix to bottom right and return back in 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 -1 * inf;
    if (dp[row1][col1][row2] != -1) return dp[row1][col1][row2];
    int ch1 = -1 * inf, ch2 = -1 * inf, 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