Số đường đi với điểm tối đa trong C++

Cho bàn cờ vuông ký tự. Bắt đầu tại góc dưới phải 'S', cần đến góc trên trái 'E'. Các ô khác: số 1-9 hoặc chướng ngại 'X'. Di chuyển: lên, trái, chéo lên-trái (nếu không phải 'X'). Tìm [max_sum, số_đường_đi] modulo 1e9+7. Trả về [0,0] nếu không có đường.

Ví dụ: board = ["E12","1X1","21S"] → [1,2].

Giải pháp

DP từ dưới phải lên trên trái (ngược hướng đi):

• dp[i][j][0] = max sum từ (i,j) đến E
• dp[i][j][1] = số đường đạt max sum
• Khởi tạo: dp[n-1][m-1] = {0,1} (ô S)
• Điền hàng cuối và cột cuối trước
• Duyệt i từ n-2 xuống 0, j từ m-2 xuống 0:
  • Nếu 'X': bỏ qua
  • Giá trị ô: 0 nếu 'E', ngược lại số nguyên
  • maxVal = max(dp[i+1][j], dp[i][j+1], dp[i+1][j+1])
  • Nếu maxVal==0 và không kề 'S': dp=0, continue
  • dp[i][j][0] += maxVal
  • Cộng số đường từ các hướng cho maxVal
  • Modulo 1e9+7
• Trả về dp[0][0]

Ví dụ mã C++

#include <bits/stdc++.h> 
using namespace std; 

void print_vector(vector<auto> v) { 
    cout << "["; 
    for(int i = 0; i < v.size(); i++) cout << v[i] << ", "; 
    cout << "]" << endl; 
} 

typedef long long int lli; 
const lli m = 1e9 + 7; 

lli add(lli a, lli b) { 
    return ((a % m) + (b % m)) % m; 
} 

class Solution { 
public: 
    vector<int> pathsWithMaxScore(vector<string>& b) { 
        int n = b.size(); 
        int 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+1][j][1]; 
                if(dp[i+1][j+1][0] == maxVal) dp[i][j][1] += dp[i+1][j+1][1]; 
                if(dp[i][j+1][0] == maxVal) dp[i][j][1] += dp[i][j+1][1]; 
                dp[i][j][1] %= m; 
                dp[i][j][0] %= m; 
            } 
        } 
        return dp[0][0]; 
    } 
}; 

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

Đầu vào

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

Đầu ra

[1, 2, ]