C++에서 검은색 픽셀을 둘러싸는 가장 작은 사각형

이미지가 있고 그 이미지가 0이 흰색 픽셀이고 1이 검은색 픽셀인 이진 행렬로 표시된다고 가정합니다. 여기에 검은색 픽셀이 연결되어 있으므로 검은색 영역이 하나만 있습니다. 픽셀은 가로와 세로로 연결됩니다. 검은색 픽셀 중 하나의 위치(x, y)가 있는 경우 모든 검은색 픽셀을 둘러싸는 가장 작은(축 정렬) 직사각형 영역을 찾아야 합니다.

따라서 입력이 다음과 같으면

x =0, y =2이면 출력은 6이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 하나의 2D 배열 정의 v

• searchRows() 함수를 정의하면 i, j, left, right, one,

  가 필요합니다.

• i

  • 중간 :=i + (j - i) / 2

  • k :=왼쪽

  • 동안 (k

    • (k를 1씩 증가)

  • k <' right가 1과 같으면 -

    • j :=중간

  • 그렇지 않으면

    • 나는 :=중간 + 1

• 반환 i

• searchColumn() 함수를 정의하면 i, j, top, bottom, one,

  가 필요합니다.

• i가 j와 같지 않은 동안 −

  • 중간 :=i + (j - i) / 2

  • k :=상단

  • 동안 (k <하단 및 v[k, mid]는 '0'과 동일), 수행 -

    • (k를 1씩 증가)

  • k <하단이 1과 같으면 -

    • j :=중간

  • 그렇지 않으면

    • 나는 :=중간 + 1

• 반환 i

• 주요 방법에서 다음을 수행하십시오 -

• v :=이미지

• ret :=0

• n :=이미지의 행 크기

• m :=이미지의 열 크기

• 상단 :=searchRows(0, x, 0, m, true)

• 하단 :=searchRows(x + 1, n, 0, m, 거짓)

• 왼쪽 :=searchColumn(0, y, 위쪽, 아래쪽, 참)

• 오른쪽 :=searchColumn(y + 1, m, 상단, 하단, 거짓)

• 리턴(오른쪽 - 왼쪽) * (하단 - 상단)

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#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