একা পিক্সেল II সমস্যা C++-এ সমাধান

একটি ছবিতে কালো ও সাদা পিক্সেল থাকলে, আমাদের এমন কালো পিক্সেলের সংখ্যা বের করতে হবে যা নির্দিষ্ট নিয়মাবলী মেনে চলে। ছবিটি একটি ২D ক্যারেক্টার অ্যারে হিসেবে দেওয়া থাকে যেখানে 'B' কালো এবং 'W' সাদা পিক্সেল বোঝায়।

নিয়মাবলী

1. পंक्ति R এবং কলাম C-এ ঠিক Nটি কালো পিক্সেল থাকবে।
2. কলাম C-এ যেসব পंক্তিতে কালো পিক্সেল আছে, সেগুলো পंक्ति R-এর সাথে একই হতে হবে।

উদাহরণ

ইনপুট ম্যাট্রিক্স:

W B W B B W
W B W B B W
W B W B B W
W W B W B W

N = 3 হলে আউটপুট: 6

কলাম ১ এবং ৩-এ থাকা সব 'B' পিক্সেলগুলো নিয়ম মেনে চলে।

অ্যালগরিদম

1. ret = 0 ইনিশিয়ালাইজ করুন।
2. দুটি ম্যাপ r (পंक्ति->কলাম সেট) এবং c (কলাম->প সেট) তৈরি করুন।
3. সম্পূর্ণ ম্যাট্রিক্স ট্রাভার্স করে 'B' পিক্সেলগুলো ম্যাপে সংরক্ষণ করুন।
4. প্রতিটি সেলের জন্য যেনি 'B' আছে, চেক করুন:
   • সেই পংতিতে ঠিক Nটি 'B' আছে কিনা।
   • সেই কলামে ঠিক Nটি 'B' আছে কিনা।
   • কলাম C-এ 'B' রেখে প Sungর সব প Sungই বর্তমান প Sungের সমান কিনা।
5. শর্ত পূরণ করলে ret বাড়ান।

C++ কোড উদাহরণ

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

class Solution {
public:
    int findBlackPixel(vector>& p, int N) {
        int ret = 0;
        unordered_map> 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> 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