資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中包圍黑色畫素的最小矩形
假設我們有一張影像，該影像由一個二進位制矩陣表示，其中 0 表示白色畫素，1 表示黑色畫素。這裡黑色畫素是連線的，所以只有一個黑色區域。畫素在水平和垂直方向上連線。如果我們有一個黑色畫素的位置 (x, y)，我們必須找到包圍所有黑色畫素的最小（軸對齊）矩形的面積。
因此，如果輸入如下所示：
| 0 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
並且 x = 0，y = 2，則輸出將為 6
為了解決這個問題，我們將遵循以下步驟：
定義一個二維陣列 v
定義一個函式 searchRows()，它將接收 i、j、left、right、one 作為引數。
當 i < j 時，執行以下操作：
mid := i + (j - i) / 2
k := left
當 (k < right 且 v[mid, k] 等於 '0') 時，執行以下操作：
(將 k 加 1)
如果 k < 'right 等於 one，則：
j := mid
否則
i := mid + 1
返回 i
定義一個函式 searchColumn()，它將接收 i、j、top、bottom、one 作為引數。
當 i 不等於 j 時，執行以下操作：
mid := i + (j - i) / 2
k := top
當 (k < bottom 且 v[k, mid] 等於 '0') 時，執行以下操作：
(將 k 加 1)
如果 k < bottom 等於 one，則：
j := mid
否則
i := mid + 1
返回 i
從主方法執行以下操作：
v := image
ret := 0
n := 影像的行大小
m := 影像的列大小
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)
返回 (right - left) * (bottom - top)
示例
讓我們看看以下實現以更好地理解：
#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
313 次檢視
