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[0].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[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; for(int i = 0; i < 4; i++){ int nx = x + dict[i][0]; int ny = y + dict[i][1]; if(nx < 0 || ny < 0 || nx >= image.size() || ny >= image[0].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; } };