C++ में लोनली पिक्सेल II

मान लीजिए हमारे पास एक तस्वीर है जिसमें काले और सफेद पिक्सेल हैं। हमें उन काले पिक्सेल की संख्या ज्ञात करनी है जो पंक्ति R और कॉलम C पर मौजूद हैं और निम्नलिखित नियमों का पालन करते हैं:

• पंक्ति R और कॉलम C में ठीक N काले पिक्सेल होंगे।
• वे सभी पंक्तियाँ जिनमें कॉलम C पर काला पिक्सेल है, वे पंक्ति R के समान होनी चाहिए।

यहाँ तस्वीर को 2D कैरेक्टर ऐरे द्वारा दर्शाया गया है जिसमें 'B' (काला) और 'W' (सफेद) होते हैं।

यदि इनपुट निम्न तालिका की तरह है:

और N = 3 है, तो आउटपुट 6 होगा। क्योंकि कॉलम 1 और 3 पर सभी बोल्ड 'B' काले पिक्सेल हैं। यदि हम पंक्ति R = 0 और कॉलम C = 1 पर 'B' लेते हैं: नियम 1 - पंक्ति R = 0 और कॉलम C = 1 दोनों में ठीक N 'B' पिक्सेल हैं। नियम 2 - जिन पंक्तियों में कॉलम C = 1 पर 'B' पिक्सेल है, वे पंक्ति 0, 1 और 2 हैं। वे पंक्ति R = 0 के समान हैं।

समाधान दृष्टिकोण

• ret := 0
• दो मैप परिभाषित करें: r (पंक्ति-वार काले पिक्सेल के कॉलम) और c (कॉलम-वार काले पिक्सेल की पंक्तियाँ)।
• n := पंक्तियों की संख्या, m := कॉलम की संख्या
• सभी सेल्स को पार करें: यदि p[i][j] == 'B' है, तो j को r[i] में और i को c[j] में डालें।
• फिर से सभी सेल्स को पार करें: यदि p[i][j] == 'B' और r[i].size() == N और c[j].size() == N है, तो:
  • ok := true
  • c[j] में प्रत्येक x के लिए: यदि r[x] != r[i] है, तो ok := false और लूप से बाहर निकलें।
  • ret += ok
• ret वापस करें।

उदाहरण (C++ कोड)

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

class Solution { 
public: 
    int findBlackPixel(vector<vector<char>>& p, int N) { 
        int ret = 0; 
        unordered_map<int, set<int>> r, c; 
        int n = p.size(); 
        int m = p[0].size(); 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m; j++) { 
                if (p[i][j] == 'B') { 
                    r[i].insert(j); 
                    c[j].insert(i); 
                } 
            } 
        } 
        for (int i = 0; i < n; i++) { 
            for (int j = 0; j < m && r.count(i); j++) { 
                if (p[i][j] == 'B' && r[i].size() == N && c[j].size() == N) { 
                    bool ok = true; 
                    for (auto& x : c[j]) { 
                        if (r[x] != r[i]) { 
                            ok = false; 
                            break; 
                        } 
                    } 
                    ret += ok; 
                } 
            } 
        } 
        return ret; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<vector<char>> v = {{'W','B','W','B','B','W'}, 
                                 {'W','B','W','B','B','W'}, 
                                 {'W','B','W','B','B','W'}, 
                                 {'W','W','B','W','B','W'}}; 
    cout << (ob.findBlackPixel(v, 3)); 
    return 0; 
}

इनपुट

{{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','B','W','B','B','W'},{'W','W','B','W','B','W'}}, 3

आउटपुट

6