Lonely Pixel II ใน C++

สมมติว่าเรามีภาพที่ประกอบด้วยพิกเซลขาวดำ เราต้องหาจำนวนพิกเซลสีดำซึ่งมีอยู่ที่แถว R และคอลัมน์ C ซึ่งสอดคล้องกับกฎต่อไปนี้ทั้งหมด –

• R และ C จะมีพิกเซลสีดำเท่ากับ N

• สำหรับแถวทั้งหมดที่มีพิกเซลสีดำที่คอลัมน์ C ควรจะเหมือนกับแถว R ทุกประการ

รูปภาพนี้แสดงโดยอาร์เรย์ถ่าน 2 มิติที่ประกอบด้วย 'B' และ 'W' สำหรับพิกเซลขาวดำตามลำดับ

หากอินพุตเป็นแบบ −

และ N =3 ผลลัพธ์จะเป็น 6 เนื่องจากตัวหนา 'B' ทั้งหมดเป็นพิกเซลสีดำทั้งหมด 'B' ที่คอลัมน์ 1 และ 3 ตอนนี้ถ้าเราเอา 'B' ที่แถว R =0 และคอลัมน์ C =1 ตัวอย่างเช่น กฎข้อที่ 1 แถว R =0 และคอลัมน์ C =1 ต่างก็มีพิกเซล N 'B' และกฎข้อที่ 2 แถวมีพิกเซล 'B' ที่คอลัมน์ C =1 คือแถว 0, แถวที่ 1 และแถวที่ 2 เหมือนกันทุกประการกับแถว R =0

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ยกเลิก :=0

• กำหนดหนึ่งแผนที่ r อีกแผนที่หนึ่ง c

• n :=จำนวนแถวของ p, m :=จำนวนคอลัมน์ของ p

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า p[i, j] เหมือนกับ 'B' แล้ว −

      • แทรก j ลงใน r[i]

      • แทรก i ลงใน c[j]

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • สำหรับการเริ่มต้น j :=0 เมื่อ j

    • ถ้า p[i, j] เท่ากับ 'B' และขนาดของ r[i] เท่ากับ N และขนาดของ c[j] เท่ากับ N ดังนั้น −

      • โอเค :=จริง

      • สำหรับแต่ละ x ใน c[j] ทำ

        • ถ้า r[x] ไม่เท่ากับ r[i] แล้ว −

          • โอเค :=เท็จ

          • ออกจากวง

      • ret :=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;
   }
};
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));
}

อินพุต

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