Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में अधिकतम स्कोर वाले पथों की संख्या

मान लीजिए हमारे पास वर्णों का एक वर्ग बोर्ड है। हम बोर्ड पर नीचे दाएं वर्ग से शुरू कर सकते हैं जिसे '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, ]
  1. - C++ में मितव्ययी संख्या (Frugal Number)

    इस समस्या में, हमें एक धनात्मक पूर्णांक N दिया गया है। हमारा कार्य यह जांचने के लिए एक प्रोग्राम बनाना है कि दी गई संख्या मितव्ययी संख्या है या नहीं। मितव्ययी संख्या (FRUGAL NUMBER) − एक संख्या जिसके अंकों की संख्या उस संख्या के अभाज्य गुणनखंडन में अंकों की संख्या से सख्ती से अधिक है। उदाहरण &

  1. C++ में पेंटाटोप संख्या C++ में पेंटाटोप संख्या

    एक पेंटाटोप संख्या को पास्कल के त्रिभुज में पांचवीं संख्या के रूप में वर्णित किया गया है। अब, चूंकि यह पांचवीं संख्या है, इसका मतलब है कि पास्कल के त्रिभुज में कम से कम पांच संख्याएं होनी चाहिए, इसलिए इस श्रृंखला की पहली संख्या 1 4 6 4 1 से शुरू होती है जो पास्कल के त्रिभुज की चौथी पंक्ति है। तो, इस

  1. - C++ में वेरिएबल बनाम वास्तविक संख्या से सरणी इनिशियलाइज़ करना

    सरणी एक ही प्रकार के एलिमेंट्स का संग्रह है जो सन्निहित मेमोरी लोकेशन पर होते हैं। सरणी में सबसे कम पता पहले एलिमेंट से मेल खाता है जबकि सबसे अधिक पता अंतिम एलिमेंट से मेल खाता है। सरणी इंडेक्स शून्य (0) से शुरू होता है और सरणी के आकार घटा एक (सरणी आकार - 1) पर समाप्त होता है। सरणी को वेरिएबल्स के स