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

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

ดังนั้นหากอินพุตเป็นแบบ

และ x =0, y =2 ผลลัพธ์จะเป็น 6

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

• กำหนดอาร์เรย์ 2 มิติ v

• กำหนดฟังก์ชัน searchRows() ซึ่งจะใช้ i, j, ซ้าย, ขวา, หนึ่ง,

• ในขณะที่ฉัน

  • กลาง :=i + (j - i) / 2

  • k :=ซ้าย

  • ในขณะที่ (k

    • (เพิ่ม k ขึ้น 1)

  • ถ้า k <' right เท่ากับหนึ่ง ดังนั้น −

    • j :=กลาง

  • มิฉะนั้น

    • ผม :=กลาง + 1

• กลับมา

• กำหนดฟังก์ชัน searchColumn() ซึ่งจะใช้ i, j, บน, ล่าง, หนึ่ง,

• ในขณะที่ฉันไม่เท่ากับ j ให้ทำ -

  • กลาง :=i + (j - i) / 2

  • k :=ด้านบน

  • ในขณะที่ (k

    • (เพิ่ม k ขึ้น 1)

  • ถ้า k

    • j :=กลาง

  • มิฉะนั้น

    • ผม :=กลาง + 1

• กลับมา

• จากวิธีหลัก ให้ทำดังต่อไปนี้ −

• v :=รูปภาพ

• ยกเลิก :=0

• n :=ขนาดแถวของรูปภาพ

• m :=ขนาด col ของรูปภาพ

• top :=searchRows(0, x, 0, m, true)

• bottom :=searchRows(x + 1, n, 0, m, false)

• ซ้าย :=searchColumn(0, y, บน, ล่าง, จริง)

• right :=searchColumn(y + 1, m, top, bottom, false)

• กลับ (ขวา - ซ้าย) * (ล่าง - บน)

ตัวอย่าง

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < vector <char> > v;
   int searchRows(int i, int j, int left, int right, bool one){
      while (i < j) {
         int mid = i + (j - i) / 2;
         int k = left;
         while (k < right && v[mid][k] == '0')
            k++;
         if (k < right == one) {
            j = mid;
         }
         else {
            i = mid + 1;
         }
      }
      return i;
   }
   int searchColumn(int i, int j, int top, int bottom, bool one){
      while (i != j) {
         int mid = i + (j - i) / 2;
         int k = top;
         while (k < bottom && v[k][mid] == '0')
            k++;
         if (k < bottom == one) {
            j = mid;
         }
         else {
            i = mid + 1;
         }
      }
      return i;
   }
   int minArea(vector<vector<char>>& image, int x, int y) {
      v = image;
      int ret = 0;
      int n = image.size();
      int 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<vector<char>> 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

ผลลัพธ์

6