Điểm đen cô đơn II trong C++

Giới thiệu

Cho một hình ảnh gồm các điểm ảnh đen ('B') và trắng ('W'), cần tìm số lượng điểm ảnh đen thỏa mãn các quy tắc sau:

• Hàng R và cột C đều chứa đúng N điểm ảnh đen.
• Tất cả các hàng có điểm ảnh đen tại cột C phải giống hệt hàng R.

Ví dụ minh họa

Đầu vào:

Với N = 3, đầu ra là 6. Các điểm 'B' đậm tại cột 1 và 3 thỏa mãn điều kiện.

Ý tưởng giải thuật

1. Sử dụng hai unordered_map: r lưu tập các cột có 'B' trên mỗi hàng, c lưu tập các hàng có 'B' trên mỗi cột.
2. Duyệt ma trận, điền dữ liệu vào r và c.
3. Duyệt lại các ô chứa 'B', kiểm tra:
   • Kích thước r[i] và c[j] đều bằng N.
   • Tất cả các hàng trong c[j] phải có tập cột 'B' giống hệt r[i].
4. Đếm số ô thỏa mãn.

Ví dụ triển khai (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;
}

Đầu vào

{{'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

Đầu ra

6