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