# [leetcode] Smallest Rectangle Enclosing Black Pixels

Smallest Rectangle Enclosing Black Pixels

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.

For example, given the following image:

```[
"0010",
"0110",
"0100"
]
```

and `x = 0`, `y = 2`,Return `6`.

A BFS approach. Find the min and max of x and y during the BFS. Mark visited cell as ‘2’ to avoid duplicate visit.

```//Can I manipulate this image?
class Solution {
public:
int minArea(vector<vector<char>>& image, int x, int y) {
if(image.size() == 0 || image.size() == 0) return 0;
queue<pair<int, int>> q;
q.push(make_pair(x, y));
image[x][y] = '2';
int left, right;
left = right = x;
int top, bottom;
top = bottom = y;
while(!q.empty()){
int x = q.front().first;
int y = q.front().second;
q.pop();
left = min(left, x);
right = max(right, x);
top = min(top, y);
bottom = max(bottom, y);
int dict[] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for(int i = 0; i < 4; i++){
int nx = x + dict[i];
int ny = y + dict[i];
if(nx < 0 || ny < 0 || nx >= image.size() || ny >= image.size()){
continue; // not valid
}
if(image[nx][ny] != '1'){
continue; // not a black pixel
}

q.push(make_pair(nx, ny));
image[nx][ny] = '2';
}
}
int width = right - left + 1;
int height = bottom - top + 1;
return width * height;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.