สี่เหลี่ยมเล็กที่สุดที่ล้อมพิกเซลสีดำใน C++

สมมติว่าเรามีภาพที่แทนด้วยเมทริกซ์ไบนารี 0 คือพิกเซลสีขาว 1 คือพิกเซลสีดำ พิกเซลสีดำเชื่อมต่อกันเป็นกลุ่มเดียว (เชื่อมต่อแนวนอนและแนวตั้ง) หากเรามีตำแหน่ง (x,y) ของพิกเซลสีดำหนึ่งจุด เราต้องหาพื้นที่ของสี่เหลี่ยมผืนผ้า (axis-aligned) ที่เล็กที่สุดซึ่งล้อมพิกเซลสีดำทั้งหมด

เช่น ถ้าอินพุตเป็นเมทริกซ์ 3x4 ตามตาราง (มีการไฮไลท์สีน้ำเงิน) และ x=0, y=2 ผลลัพธ์จะเป็น 6

ในการแก้ปัญหานี้ เราจะใช้ Binary Search หาขอบเขต 4 ด้าน ทำตามขั้นตอน:

กำหนดอาร์เรย์ v = image
ฟังก์ชัน searchRows(i,j,left,right,one): binary search หาแถวบนสุด/ล่างสุดที่มีพิกเซล 1 ในช่วงคอลัมน์ left..right-1
ฟังก์ชัน searchColumn(i,j,top,bottom,one): binary search หาคอลัมน์ซ้ายสุด/ขวาสุดที่มีพิกเซล 1 ในช่วงแถว top..bottom-1
จาก main: top = searchRows(0,x,0,m,true); bottom = searchRows(x+1,n,0,m,false); left = searchColumn(0,y,top,bottom,true); right = searchColumn(y+1,m,top,bottom,false); คืนค่า (right-left)*(bottom-top)

ตัวอย่าง

ลองดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น:

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    vector> v;
    int searchRows(int i, int j, int left, int right, bool one){
        while(i>& image, int x, int y) {
        v = image;
        int n = image.size(), m = image[0].size();
        int top = searchRows(0, x, 0, m, true);
        int bottom = searchRows(x+1, n, 0, m, false);
        int left = searchColumn(0, y, top, bottom, true);
        int right = searchColumn(y+1, m, top, bottom, false);
        return (right-left)*(bottom-top);
    }
};
main(){
    Solution ob;
    vector> v = {{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}};
    cout << (ob.minArea(v, 0, 2));
}

อินพุต

{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}, 0, 2

สี่เหลี่ยมเล็กที่สุดที่ล้อมพิกเซลสีดำใน C++

ตัวอย่าง

อินพุต

เอาต์พุต