จำนวนเส้นทางคะแนนสูงสุดใน C++

คำอธิบายโจทย์

บอร์ดสี่เหลี่ยม เริ่ม 'S' มุมล่างขวา ถึง 'E' มุมบนซ้าย เดินได้: บน, ซ้าย, ทแยงบนซ้าย เฉพาะไม่ใช่ 'X' หา: [max_sum, จำนวนเส้นทางที่ได้ max_sum] mod 1e9+7

ตัวอย่าง

board = ["E12","1X1","21S"] → Output: [1,2]

วิธีแก้ปัญหา

DP 3 มิติ dp[i][j][0]=max_sum, dp[i][j][1]=count จาก (i,j) ไป (0,0):

1. เริ่ม dp[n-1][m-1] = {0,1}
2. เติมแถวล่างสุดและคอลัมน์ขวาสุด
3. DP กลับ: dp[i][j] มาจาก max ของ 3 ทิศทาง บวกค่าปัจจุบัน
4. นับจำนวนทางที่ให้ max เท่ากัน

การทำงานของโค้ด

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const lli MOD = 1e9+7;

class Solution {
public:
    vector<int> pathsWithMaxScore(vector<string>& b) {
        int n = b.size(), m = b[0].size();
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(m, vector<int>(2)));
        
        dp[n-1][m-1][0] = 0; dp[n-1][m-1][1] = 1;
        
        // แถวล่างสุด
        for(int i=m-2; i>=0; i--) {
            if(b[n-1][i]=='X') break;
            dp[n-1][i][0] = b[n-1][i]-'0' + dp[n-1][i+1][0];
            dp[n-1][i][1] += dp[n-1][i+1][1];
        }
        // คอลัมน์ขวาสุด
        for(int i=n-2; i>=0; i--) {
            if(b[i][m-1]=='X') break;
            dp[i][m-1][0] = b[i][m-1]-'0' + dp[i+1][m-1][0];
            dp[i][m-1][1] += dp[i+1][m-1][1];
        }
        // กลาง
        for(int i=n-2; i>=0; i--) {
            for(int j=m-2; j>=0; j--) {
                if(b[i][j]=='X') continue;
                dp[i][j][0] = (b[i][j]=='E') ? 0 : b[i][j]-'0';
                int maxVal = max({dp[i][j+1][0], dp[i+1][j][0], dp[i+1][j+1][0]});
                if(maxVal==0 && b[i+1][j]!='S' && b[i][j+1]!='S' && b[i+1][j+1]!='S') {
                    dp[i][j][0]=0; continue;
                }
                dp[i][j][0] += maxVal;
                if(dp[i+1][j][0]==maxVal) dp[i][j][1] = (dp[i][j][1]+dp[i+1][j][1])%MOD;
                if(dp[i+1][j+1][0]==maxVal) dp[i][j][1] = (dp[i][j][1]+dp[i+1][j+1][1])%MOD;
                if(dp[i][j+1][0]==maxVal) dp[i][j][1] = (dp[i][j][1]+dp[i][j+1][1])%MOD;
            }
        }
        return dp[0][0];
    }
};

int main() {
    Solution ob;
    vector<string> v = {"E12","1X1","21S"};
    auto ans = ob.pathsWithMaxScore(v);
    cout << "[" << ans[0] << ", " << ans[1] << "]";
    return 0;
}

อินพุต

{"E12","1X1","21S"}

เอาต์พุต

[1, 2]