-
Notifications
You must be signed in to change notification settings - Fork 22
/
600.smallest-rectangle-enclosing-black-pixels.cpp
82 lines (77 loc) · 2.58 KB
/
600.smallest-rectangle-enclosing-black-pixels.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
// Tag: Binary Search on Answer, Binary Search
// Time: O(N * logM + M * logN)
// Space: O(1)
// Ref: -
// Note: Graph | Leetcode-302
// An image is represented by a binary matrix with `0` as a white pixel and `1` as a black pixel.
// The black pixels are connected, i.e., there is only one black region.
// Pixels are connected horizontally and vertically.
// Given the location `(x, y)` of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
//
// ---
//
// **Example 1:**
// ```
// Input:["0010","0110","0100"],x=0,y=2
// Output:6
// Explanation:
// The upper left coordinate of the matrix is (0,1), and the lower right coordinate is (2,2).
// ```
//
// **Example 2:**
// ```
// Input:["1110","1100","0000","0000"], x = 0, y = 1
// Output:6
// Explanation:
// The upper left coordinate of the matrix is (0, 0), and the lower right coordinate is (1,2).
// ```
//
//
class Solution {
public:
/**
* @param image: a binary matrix with '0' and '1'
* @param x: the location of one of the black pixels
* @param y: the location of one of the black pixels
* @return: an integer
*/
int minArea(vector<vector<char>> &image, int x, int y) {
// write your code here
int left = search(image, 0, y, checkCol, false);
int right = search(image, y, image[0].size(), checkCol, true);
int top = search(image, 0, x, checkRow, false);
int bottom = search(image, x, image.size(), checkRow, true);
return (right - left) * (bottom - top);
}
static bool checkRow(vector<vector<char>> &image, int row, bool oppsite) {
bool isIsland = false;
for (auto &point : image[row]) {
if (point == '1') {
isIsland = true;
break;
}
}
return oppsite ? !isIsland : isIsland;
}
static bool checkCol(vector<vector<char>> &image, int col, bool oppsite) {
bool isIsland = false;
for (auto &row : image) {
if (row[col] == '1') {
isIsland = true;
break;
}
}
return oppsite ? !isIsland : isIsland;
}
int search(vector<vector<char>> &image, int start, int end, bool (*check)(vector<vector<char>> &, int, bool), bool opposite) {
while (start < end) {
int mid = start + (end - start) / 2;
if (check(image, mid, opposite)) {
end = mid;
} else {
start = mid + 1;
}
}
return start;
}
};