Điểm ảnh đen bao quanh hình chữ nhật nhỏ nhất trong C ++

Giả sử chúng ta có một hình ảnh và hình ảnh đó được biểu diễn bằng ma trận nhị phân với 0 là pixel trắng và 1 là pixel đen. Ở đây các điểm ảnh màu đen được kết nối với nhau, vì vậy chỉ có một vùng màu đen. Các điểm ảnh được kết nối theo chiều ngang và chiều dọc. Nếu chúng ta có vị trí (x, y) của một trong các điểm ảnh màu đen, chúng ta phải tìm diện tích của hình chữ nhật nhỏ nhất (căn theo trục) bao quanh tất cả các điểm ảnh màu đen.

Vì vậy, nếu đầu vào giống như

và x =0, y =2, thì đầu ra sẽ là 6

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một mảng 2D v

• Xác định một hàm searchRows (), điều này sẽ lấy i, j, left, right, one,

• trong khi tôi

  • giữa:=i + (j - i) / 2

  • k:=left

  • while (k

    • (tăng k lên 1)

  • nếu k <'phải giống một, thì -

    • j:=mid

  • Nếu không

    • i:=mid + 1

• trả lại tôi

• Xác định một hàm searchColumn (), điều này sẽ lấy i, j, top, bottom, one,

• trong khi tôi không bằng j, hãy làm -

  • giữa:=i + (j - i) / 2

  • k:=top

  • while (k

    • (tăng k lên 1)

  • nếu k

    • j:=mid

  • Nếu không

    • i:=mid + 1

• trả lại tôi

• Từ phương thức chính, thực hiện như sau -

• v:=hình ảnh

• ret:=0

• n:=kích thước hàng của hình ảnh

• m:=kích thước col của hình ảnh

• 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)

• return (phải - trái) * (dưới - trên)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

Đầu ra

6