मान लीजिए हमारे पास वर्णों का एक वर्ग बोर्ड है। हम बोर्ड पर नीचे दाएं वर्ग से शुरू कर सकते हैं जिसे 'S' वर्ण से चिह्नित किया गया है। अब हमें ऊपर बाएं वर्ग तक पहुंचने की आवश्यकता है जिसे 'E' वर्ण से चिह्नित किया गया है। अन्य वर्ग या तो 1 से 9 तक के संख्यात्मक वर्ण से लेबल किए गए हैं या बाधा 'X' से। एक चाल में हम केवल ऊपर, बाएं या ऊपर-बाएं जा सकते हैं जब वहां कोई बाधा न हो।
हमें दो संख्याओं की सूची ज्ञात करनी है: पहली संख्या हमारे द्वारा एकत्र किए जा सकने वाले संख्यात्मक वर्णों का अधिकतम योग है, और दूसरी वह पथों की संख्या है जिनसे हम उस अधिकतम योग को प्राप्त कर सकते हैं। उत्तर को मॉड्यूलो 10^9 + 7 पर लौटाएं। जब कोई पथ नहीं है, तो [0, 0] लौटाएं।
यदि इनपुट board = ["E12","1X1","21S"] है, तो आउटपुट [1,2] होगा।
हल करने के चरण
n := पंक्तियों की संख्या, m := स्तंभों की संख्या
आकार n x m x 2 का एक 3D सरणी dp परिभाषित करें
dp[n-1][m-1][0] = 0, dp[n-1][m-1][1] = 1
अंतिम पंक्ति और अंतिम स्तंभ को भरें
शेष सेल्स के लिए: यदि 'X' नहीं है, तो तीन दिशाओं (दाएं, नीचे, विकर्ण) से अधिकतम मान और पथों की संख्या की गणना करें
dp[0][0] लौटाएं
उदाहरण
#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;
}
इनपुट
{"E12","1X1","21S"}
आउटपुट
[1, 2, ]