// dfs
func minArea(image [][]byte, x int, y int) int {
m, n := len(image), len(image[0])
xMin, xMax, yMin, yMax := m, 0, n, 0
var dfs func(i, j int)
dfs = func(x, y int) {
if x < 0 || y < 0 || x == m || y == n || image[x][y] != '1' {
return
}
if x < xMin {
xMin = x
}
if x > xMax {
xMax = x
}
if y < yMin {
yMin = y
}
if y > yMax {
yMax = y
}
image[x][y] = '0'
dfs(x+1, y)
dfs(x-1, y)
dfs(x, y+1)
dfs(x, y-1)
}
dfs(x, y)
return (xMax - xMin + 1) * (yMax - yMin + 1)
}
// 二分查找
func minArea3(image [][]byte, x int, y int) int {
m, n := len(image), len(image[0])
xMin := findXExtremum(image, 0, x, true)
xMax := findXExtremum(image, x, m-1, false)
yMin := findYExtremum(image, 0, y, true)
yMax := findYExtremum(image, y, n-1, false)
return (xMax - xMin + 1) * (yMax - yMin + 1)
}
func findXExtremum(image [][]byte, l, r int, min bool) int {
for l <= r {
mid := (r-l)/2 + l
found := false
for _, b := range image[mid] {
if b == '1' {
found = true
break
}
}
if found == min {
r = mid - 1
} else {
l = mid + 1
}
}
if min {
return l
}
return r
}
func findYExtremum(image [][]byte, l, r int, min bool) int {
for l <= r {
mid := (r-l)/2 + l
found := false
for _, row := range image {
if row[mid] == '1' {
found = true
break
}
}
if found == min {
r = mid - 1
} else {
l = mid + 1
}
}
if min {
return l
}
return r
}
class Solution {
public int minArea(char[][] image, int x, int y) {
int top = x, bottom = x;
int left = y, right = y;
for (x = 0; x < image.length; ++x) {
for (y = 0; y < image[0].length; ++y) {
if (image[x][y] == '1') {
top = Math.min(top, x);
bottom = Math.max(bottom, x + 1);
left = Math.min(left, y);
right = Math.max(right, y + 1);
}
}
}
return (right - left) * (bottom - top);
}
}
class Solution2 {
private int top, bottom, left, right;
public int minArea(char[][] image, int x, int y) {
if(image.length == 0 || image[0].length == 0) return 0;
top = bottom = x;
left = right = y;
dfs(image, x, y);
return (right - left) * (bottom - top);
}
private void dfs(char[][] image, int x, int y){
if(x < 0 || y < 0 || x >= image.length || y >= image[0].length ||
image[x][y] == '0')
return;
image[x][y] = '0'; // 将访问过的黑色像素标记为白色
top = Math.min(top, x);
bottom = Math.max(bottom, x + 1);
left = Math.min(left, y);
right = Math.max(right, y + 1);
dfs(image, x + 1, y);
dfs(image, x - 1, y);
dfs(image, x, y - 1);
dfs(image, x, y + 1);
}
}
class Solution3 {
public int minArea(char[][] image, int x, int y) {
int m = image.length, n = image[0].length;
int left = searchColumns(image, 0, y, 0, m, true);
int right = searchColumns(image, y + 1, n, 0, m, false);
int top = searchRows(image, 0, x, left, right, true);
int bottom = searchRows(image, x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
private int searchColumns(char[][] image, int i, int j, int top, int bottom, boolean whiteToBlack) {
while (i != j) {
int k = top, mid = (i + j) / 2;
while (k < bottom && image[k][mid] == '0') ++k;
if (k < bottom == whiteToBlack) // k < bottom 意味着 mid 列中有黑色像素
j = mid; //在较小的一半中搜索边界
else
i = mid + 1; //在较大的一半中搜索边界
}
return i;
}
private int searchRows(char[][] image, int i, int j, int left, int right, boolean whiteToBlack) {
while (i != j) {
int k = left, mid = (i + j) / 2;
while (k < right && image[mid][k] == '0') ++k;
if (k < right == whiteToBlack) // k < right means 意味着 mid 行中有黑色像素
j = mid;
else
i = mid + 1;
}
return i;
}
}
class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
int Row = image.size();
int Col = image[0].size();
int lo, hi;
lo = 0, hi = x;
while (lo < hi)
{
int mid = (lo + hi) / 2;
int c = 0;
while (c < Col && image[mid][c] == '0') c ++;
if (c < Col)
hi = mid;
else
lo = mid + 1;
}
int Up = lo;
lo = x, hi = Row - 1;
while (lo < hi)
{
int mid = (lo + hi + 1) / 2;
int c = 0;
while (c < Col && image[mid][c] == '0') c ++;
if (c < Col)
lo = mid;
else
hi = mid - 1;
}
int Down = lo;
lo = 0, hi = y;
while (lo < hi)
{
int mid = (lo + hi) / 2;
int r = 0;
while (r < Row && image[r][mid] == '0') r ++;
if (r < Row)
hi = mid;
else
lo = mid + 1;
}
int Left = lo;
lo = y, hi = Col - 1;
while(lo < hi)
{
int mid = (lo + hi + 1) / 2;
int r = 0;
while (r < Row && image[r][mid] == '0') r ++;
if (r < Row)
lo = mid;
else
hi = mid - 1;
}
int Right = lo;
return (Down - Up + 1) * (Right - Left + 1);
}
int minArea2(vector<vector<char>>& image, int x, int y) {
//遍历 roc坐标
int Row = image.size();
int Col = image[0].size();
int Up = x, Down = x;
int Left = y, Right = y;
bool visited[Row][Col]; memset(visited, 0, sizeof(visited));
std::function<void(int,int)> dfs = [&] (int r, int c)
{
Up = min(Up, r);
Down = max(Down, r);
Left = min(Left, c);
Right = max(Right, c);
for (auto [nr, nc]: vector<pair<int,int>>{{r-1,c}, {r+1,c}, {r,c-1}, {r,c+1}})
{
if (0 <= nr && nr < Row && 0 <= nc && nc < Col)
{
if (visited[nr][nc] == false && image[nr][nc] == '1')
{
visited[nr][nc] = true;
dfs(nr, nc);
}
}
}
};
visited[x][y] = true;
dfs(x, y);
return (Down - Up + 1) * (Right - Left + 1);
}
};
class Solution:
def minArea(self, image: List[List[str]], x: int, y: int) -> int:
#遍历，更新 用roc坐标
Row, Col = len(image), len(image[0])
Up = x
Down = x
Left = y
Rgiht = y
for r in range(Row):
for c in range(Col):
if image[r][c] == '1':
Up = min(Up, r)
Down = max(Down, r)
Left = min(Left, c)
Rgiht = max(Rgiht, c)
return (Down - Up + 1) * (Rgiht - Left + 1)
def minArea2(self, image: List[List[str]], x: int, y: int) -> int:
#遍历，更新 用roc坐标
Row, Col = len(image), len(image[0])
Up = x
Down = x
Left = y
Rgiht = y
#------------- bfs + 记忆化
Q = collections.deque()
visited = [[False for _ in range(Col)] for _ in range(Row)]
Q.append((x, y))
visited[x][y] = True
while Q:
r, c = Q.popleft()
Up = min(Up, r)
Down = max(Down, r)
Left = min(Left, c)
Rgiht = max(Rgiht, c)
for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
if 0 <= nr < Row and 0 <= nc < Col:
if visited[nr][nc] == False and image[nr][nc] == '1':
visited[nr][nc] = True
Q.append((nr, nc))
return (Down - Up + 1) * (Rgiht - Left + 1)
def minArea3(self, image: List[List[str]], x: int, y: int) -> int:
#遍历，更新 用roc坐标
Row, Col = len(image), len(image[0])
self.Up = x
self.Down = x
self.Left = y
self.Rgiht = y
#------------- dfs + 记忆化
visited = [[False for _ in range(Col)] for _ in range(Row)]
def dfs(r: int, c: int) -> None:
self.Up = min(self.Up, r)
self.Down = max(self.Down, r)
self.Left = min(self.Left, c)
self.Rgiht = max(self.Rgiht, c)
for nr, nc in [(r-1,c), (r+1,c), (r,c-1), (r,c+1)]:
if 0 <= nr < Row and 0 <= nc < Col:
if visited[nr][nc] == False and image[nr][nc] == '1':
visited[nr][nc] = True
dfs(nr, nc)
visited[x][y] = True
dfs(x, y)
return (self.Down - self.Up + 1) * (self.Rgiht - self.Left + 1)
def minArea4(self, image: List[List[str]], x: int, y: int) -> int:
#遍历，更新 用roc坐标
Row, Col = len(image), len(image[0])
lo, hi = 0, x
while lo < hi:
mid = (lo + hi) // 2
c = 0
while c < Col and image[mid][c] == '0': c += 1
if c < Col:
hi = mid
else:
lo = mid + 1
Up = lo
lo, hi = x, Row - 1
while lo < hi:
mid = (lo + hi + 1) // 2
c = 0
while c < Col and image[mid][c] == '0': c += 1
if c < Col:
lo = mid
else:
hi = mid - 1
Down = lo
lo, hi = 0, y
while lo < hi:
mid = (lo + hi) // 2
r = 0
while r < Row and image[r][mid] == '0': r += 1
if r < Row:
hi = mid
else:
lo = mid + 1
Left = lo
lo, hi = y, Col - 1
while lo < hi:
mid = (lo + hi + 1) // 2
r = 0
while r < Row and image[r][mid] == '0': r += 1
if r < Row:
lo = mid
else:
hi = mid - 1
Right = lo
return (Down - Up + 1) * (Right - Left + 1)
