C++ प्रोग्राम: ग्रिड में सफाई रोबोट द्वारा साफ किए जा सकने वाले अधिकतम सेल्स की संख्या

समस्या विवरण

हम एक सफाई रोबोट बना रहे हैं जो ग्रिड पर काम करता है। ग्रिड का आकार h x w है। m गंदे सेल हैं जिन्हें साफ करने की आवश्यकता है, जो पूर्णांक युग्मों के सरणी 'dirt' में दिए गए हैं। यदि सफाई रोबोट किसी विशेष सेल पर रखा जाता है, तो वह उस विशेष पंक्ति और स्तंभ के प्रत्येक सेल को साफ कर सकता है। हमारा कार्य गंदे सेल की अधिकतम संख्या को साफ करना है। हमें गिनती ज्ञात करके आउटपुट के रूप में प्रदर्शित करनी है।

उदाहरण

इनपुट: h = 3, w = 3, m = 3, dirt = {{0, 0}, {1, 1}, {2, 1}}

आउटपुट: 3

व्याख्या: यदि हम सफाई रोबोट को सेल {1, 0} पर रखते हैं, तो यह ग्रिड के सभी गंदे सेल को साफ कर सकेगा।

हल का दृष्टिकोण

1. पंक्तियों और स्तंभों में गंदे सेल गिनें - hcount[row] और wcount[col] सरणियों का उपयोग करें
2. अधिकतम गिनती खोजें - maxh (अधिकतम गंदे सेल वाली पंक्ति) और maxw (अधिकतम गंदे सेल वाला स्तंभ)
3. उम्मीदवार पंक्तियाँ और स्तंभ खोजें - वे पंक्तियाँ जिनमें maxh गंदे सेल हैं, और वे स्तंभ जिनमें maxw गंदे सेल हैं
4. प्रतिच्छेदन जांचें - यदि कोई उम्मीदवार पंक्ति और स्तंभ का प्रतिच्छेदन गंदा नहीं है, तो उत्तर maxh + maxw है, अन्यथा maxh + maxw - 1

एल्गोरिदम

// 1. प्रत्येक पंक्ति और स्तंभ में गंदे सेल गिनें
for each (r, c) in dirt:
    hcount[r]++
    wcount[c]++
    mark (r, c) as dirty

// 2. अधिकतम गिनती खोजें
maxh = max(hcount)
maxw = max(wcount)

// 3. अधिकतम गिनती वाली पंक्तियाँ और स्तंभ एकत्र करें
rows_with_maxh = {r | hcount[r] == maxh}
cols_with_maxw = {c | wcount[c] == maxw}

// 4. जांचें कि क्या कोई प्रतिच्छेदन साफ है
for r in rows_with_maxh:
    for c in cols_with_maxw:
        if (r, c) is not dirty:
            return maxh + maxw

// 5. सभी प्रतिच्छेदन गंदे हैं
return maxh + maxw - 1

C++ कार्यान्वयन

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

int solve(int h, int w, int m, vector<pair<int, int>> dirt) {
    map<pair<int, int>, int> dirty_cells;
    vector<int> hcount(h, 0), wcount(w, 0);
    
    for (int i = 0; i < m; i++) {
        int r = dirt[i].first;
        int c = dirt[i].second;
        dirty_cells[{r, c}] = 1;
        hcount[r]++;
        wcount[c]++;
    }
    
    int maxh = 0, maxw = 0;
    for (int i = 0; i < h; i++) maxh = max(maxh, hcount[i]);
    for (int i = 0; i < w; i++) maxw = max(maxw, wcount[i]);
    
    vector<int> best_rows, best_cols;
    for (int i = 0; i < h; i++) 
        if (hcount[i] == maxh) best_rows.push_back(i);
    for (int i = 0; i < w; i++) 
        if (wcount[i] == maxw) best_cols.push_back(i);
    
    for (int r : best_rows) {
        for (int c : best_cols) {
            if (!dirty_cells.count({r, c})) {
                return maxh + maxw;
            }
        }
    }
    
    return maxh + maxw - 1;
}

int main() {
    int h = 3, w = 3, m = 3;
    vector<pair<int, int>> dirt = {{0, 0}, {1, 1}, {2, 1}};
    cout << solve(h, w, m, dirt);
    return 0;
}

इनपुट

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

आउटपुट

3

जटिलता विश्लेषण

• समय जटिलता: O(m + h + w + R×C) जहां R = maxh वाली पंक्तियों की संख्या, C = maxw वाले स्तंभों की संख्या
• स्पेस जटिलता: O(h + w + m)