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

ग्रिड में सम-मूल्य वाली सेल्स की संख्या को अधिकतम करने के लिए आवश्यक ऑपरेशन्स की संख्या ज्ञात करने का C++ प्रोग्राम


मान लीजिए हमें h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की प्रत्येक सेल का एक विशिष्ट मान है। हमें सम मान वाली सेल्स की संख्या को अधिकतम करना है। इसके लिए हम एक ऐसी सेल चुन सकते हैं जिसे पहले नहीं चुना गया हो, फिर उस सेल का मान 1 घटा दें और उसके लंबवत या क्षैतिज रूप से आसन्न किसी अन्य सेल का मान 1 बढ़ा दें। हमें ऑपरेशन्स की संख्या और वृद्धि/कमी वाली सेल्स की स्थितियाँ प्रिंट करनी हैं। आउटपुट का प्रारूप निम्न होगा:

  • ऑपरेशन्स की संख्या
  • पहला (घटी हुई सेल की स्थिति) - (बढ़ी हुई सेल की स्थिति)
  • ...
  • n-वाँ (घटी हुई सेल की स्थिति) - (बढ़ी हुई सेल की स्थिति)

उदाहरण के लिए, यदि इनपुट है h = 3, w = 3, grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}, तो आउटपुट होगा:

4 (0, 1) - (0, 2) (2, 0) - (2, 1) (2, 1) - (2, 2) (0, 2) - (1, 2)

चरण

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:

एक नया सरणी result परिभाषित करें जिसमें टपल्स हों
i := 0 से प्रारंभ करें, जब i < h, i को 1 से बढ़ाते हुए:
    tp := 0
    j := 0 से प्रारंभ करें, जब j < w, j को 1 से बढ़ाते हुए:
        यदि tp > 0, तो:
            टपल (i, j-1, i, j) को result के अंत में डालें
            grid[i][j] := grid[i][j] + tp
        यदि grid[i][j] % 2 == 1 और j < w-1, तो:
            grid[i][j] := grid[i][j] - 1
            tp := 1
        अन्यथा
            tp := 0
tp := 0
i := 0 से प्रारंभ करें, जब i < h, i को 1 से बढ़ाते हुए:
    यदि tp > 0, तो:
        टपल (i-1, w-1, i, w-1) को result के अंत में डालें
        grid[i][w-1] := grid[i][w-1] + tp
    यदि grid[i][w-1] % 2 == 1, तो:
        grid[i][w-1] := grid[i][w-1] - 1
        tp := 1
    अन्यथा
        tp := 0
result के आकार को प्रिंट करें
i := 0 से प्रारंभ करें, जब i < result का आकार, i को 1 से बढ़ाते हुए:
    प्रिंट करें '(' + result[i] का पहला मान + ',' + दूसरा मान + ')' + ' - ' + '(' + तीसरा मान + ',' + चौथा मान + ')'

उदाहरण

बेहतर समझ के लिए निम्न कार्यान्वयन देखें:

#include <bits/stdc++.h> using namespace std; void solve(int h, int w, vector<vector<int>>grid){    vector<tuple<int,int,int,int>> result;    for(int i = 0; i < h; i++){       int tp = 0;       for(int j = 0; j < w; j++){          if(tp > 0){             result.push_back(make_tuple(i, j-1, i, j));             grid[i][j] += tp;          }          if(grid[i][j]%2 == 1 && j < w-1){             grid[i][j] -= 1;             tp = 1;          }          else             tp = 0;       }    }    int tp = 0;    for(int i = 0; i < h; i++){       if(tp > 0){          result.push_back(make_tuple(i-1, w-1, i, w-1));          grid[i][w-1] += tp;       }       if(grid[i][w-1]%2 == 1){          grid[i][w-1] -= 1;          tp = 1;       }       else          tp = 0;    }    cout << (int)result.size() << endl;    for(int i = 0; i < (int)result.size(); i++){       cout << "(" << get<0>(result[i]) << ", " << get<1>(result[i])       << ")" << " - (" << get<2>(result[i]) << ", " << get<3>(result[i]) << ")"; cout << '\n'; } } int main() { int h = 3, w = 3 ; vector<vector<int>> grid = {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}; solve(h, w, grid); return 0; }

इनपुट

3, 3, {{2, 3, 4}, {2, 0, 1}, {1, 2, 3}}

आउटपुट

4 (0, 1) - (0, 2) (2, 0) - (2, 1) (2, 1) - (2, 2) (0, 2) - (1, 2)
  1. ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में रोशन सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड दिया गया है। ग्रिड की सेल्स में बल्ब या बाधाएँ हो सकती हैं। एक बल्ब सेल स्वयं और अपने दाएँ, बाएँ, ऊपर, नीचे की सेल्स को रोशन करता है। प्रकाश सेल्स के माध्यम से चमकता है जब तक कि कोई बाधा सेल इसे न रोक दे। बाधा सेल न तो रोशन हो सकती है और न ही प्रकाश को गुजरने देती ह

  1. दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम दिए गए ग्राफ में ब्रिज एज की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए n वर्टेक्स और m एज वाला एक अनभारित, निदेश रहित ग्राफ दिया गया है। ग्राफ में एक ब्रिज एज वह एज है जिसे हटाने से ग्राफ असंबद्ध हो जाता है। हमें दिए गए ग्राफ में ऐसी एज की संख्या ज्ञात करनी है। ग्राफ में समानांतर एज या सेल्फ-लूप नहीं हैं। उदाहरण के लिए, यदि इनपुट है n = 5, m = 6, edges = {{1

  1. ग्रिड में पथ बनाने के लिए ब्लॉक की जाने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम ग्रिड में पथ बनाने के लिए ब्लॉक की जाने वाली सेल्स की संख्या ज्ञात करने का C++ प्रोग्राम

    मान लीजिए h × w आयाम का एक ग्रिड है। रोबोट सेल (0, 0) पर है और उसे (h-1, w-1) तक पहुँचना है। ग्रिड में दो प्रकार की सेल्स हैं: ब्लॉक और अनब्लॉक। रोबोट अनब्लॉक सेल्स से गुजर सकता है लेकिन ब्लॉक सेल्स से नहीं। रोबोट चार दिशाओं में जा सकता है: बाएँ, दाएँ, ऊपर, नीचे। लेकिन रोबोट किसी सेल से दूसरी सेल म