สมมติว่าเรามีภาพที่ประกอบด้วยพิกเซลสีดำและขาว เราต้องหาจำนวนพิกเซลสีดำที่อยู่ที่แถว R และคอลัมน์ C ซึ่งสอดคล้องกับกฎต่อไปนี้:
แถว R และคอลัมน์ C ต้องมีพิกเซลสีดำทั้งหมด N ตัว
สำหรับทุกแถวที่มีพิกเซลสีดำที่คอลัมน์ C พวกเขาต้องเหมือนกับแถว R ทุกประการ
ภาพถูกแทนด้วยอาร์เรย์ 2D ของตัวอักษร 'B' และ 'W' สำหรับพิกเซลสีดำและขาวตามลำดับ
ถ้าอินพุตเป็นดังนี้:
| 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 และ 3 ถ้าเราเลือก 'B' ที่แถว R = 0 และคอลัมน์ C = 1 ตัวอย่างเช่น: กฎที่ 1 แถว R = 0 และคอลัมน์ C = 1 ทั้งคู่มีพิกเซล 'B' อย่างแม่นยำ N ตัว และกฎที่ 2 แถวที่มีพิกเซล 'B' ที่คอลัมน์ C = 1 คือแถว 0, 1 และ 2 พวกเขาเหมือนกับแถว R = 0 ทุกประการ
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนต่อไปนี้:
ret := 0
กำหนดแมป r และแมป c
n := จำนวนแถวของ p, m := จำนวนคอลัมน์ของ p
ลูป i จาก 0 ถึง n-1:
ลูป j จาก 0 ถึง m-1:
ถ้า p[i][j] เป็น 'B' ให้:
เพิ่ม j เข้า r[i]
เพิ่ม i เข้า c[j]
ลูป i จาก 0 ถึง n-1:
ลูป j จาก 0 ถึง m-1 และ i อยู่ใน r:
ถ้า p[i][j] เป็น 'B' และขนาดของ r[i] เท่ากับ N และขนาดของ c[j] เท่ากับ N ให้:
ok := true
สำหรับแต่ละ x ใน c[j] ให้ทำ:
ถ้า r[x] ไม่เท่ากับ r[i] ให้:
ok := false
ออกจากลูป
ret := 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; } }; 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
