C ++中最小的包围黑色像素的矩形

假设我们有一个图像，并且该图像由一个二进制矩阵表示，0为白色像素，1为黑色像素。这里黑色像素相连，因此只有一个黑色区域。像素水平和垂直连接。如果我们具有黑色像素之一的位置(x,y)，则必须找到包围所有黑色像素的最小（与轴对齐）矩形的区域。

所以，如果输入像

并且x = 0，y = 2，则输出将为6

为了解决这个问题，我们将遵循以下步骤-

• 定义一个2D数组v

• 定义一个函数searchRows()，它将使用i，j，左，右，一个，

• 当我<j时-

• 我：=中+ 1

• j：=中

• （将k增加1）

• 中：= i +(j-i)/ 2

• k：=左

• 而（k <右，v [mid，k]与“ 0”相同），则执行-

• 如果k <'right与1相同，则-

• 除此以外

• 还给我

• 定义一个函数searchColumn()，它将使用i，j，top，bottom，one，

• 当我不等于j时，-

• 我：=中+ 1

• j：=中

• （将k增加1）

• 中：= i +(j-i)/ 2

• k：=顶部

• 而（k <bottom和v [k，mid]与'0'相同），做-

• 如果k <bottom与一相同，则-

• 除此以外

• 还给我

• 从主要方法中执行以下操作-

• v：=图片

• ret：= 0

• n：=图片的行大小

• m：=图片大小

• 顶部：= searchRows(0,x,0,m,true)

• 底部：= searchRows（x + 1，n，0，m，false）

• 左：= searchColumn(0,y,top,bottom,true)

• 右：= 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