​LeetCode刷题实战302：包含全部黑色像素的最小矩阵

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

今天和大家聊的问题叫做 包含全部黑色像素的最小矩阵，我们先来看题面：

https://leetcode-cn.com/problems/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.

图片在计算机处理中往往是使用二维矩阵来表示的。

假设，这里我们用的是一张黑白的图片，那么 0 代表白色像素，1 代表黑色像素。

其中黑色的像素他们相互连接，也就是说，图片中只会有一片连在一块儿的黑色像素（像素点是水平或竖直方向连接的）。

那么，给出某一个黑色像素点 (x, y) 的位置，你是否可以找出包含全部黑色像素的最小矩形（与坐标轴对齐）的面积呢？

示例

示例:
输入:
[
  "0010",
  "0110",
  "0100"
]
和 x = 0, y = 2

输出: 6

解题

找最小矩形的面积，可以转化为找所有黑色像素的X, Y坐标极值，这个面积应该等于:(x2-x1+1)*(y2-y1+1)

所以一趟DFS可以找到所有黑色的点，找到每个点的时候刷新一下极值即可。

class Solution {
    int x1 = INT_MAX, x2 = -1;
    int y1 = INT_MAX, y2 = -1;
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
      int m = image.size(), n = image[0].size(), i, j, nx, ny, k;
        vector<vector<int>> dir = {{1,0},{0,1},{0,-1},{-1,0}};
        queue<vector<int>> q;
        q.push({x,y});
        image[x][y] = '0';//访问过了
        while(!q.empty())
        {
          i = q.front()[0];
          j = q.front()[1];
          q.pop();
          x1 = min(x1, i);
          x2 = max(x2, i);
          y1 = min(y1, j);
          y2 = max(y2, j);
          for(k = 0; k < 4; ++k)
          {
            nx = i + dir[k][0];
            ny = j + dir[k][1];
            if(nx>=0 && nx<m && ny>=0 && ny<n && image[nx][ny]=='1')
            {
              q.push({nx, ny});
              image[nx][ny] = '0';//访问过了
            }
          }
        }
        return (x2-x1+1)*(y2-y1+1);
    }
};

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。

上期推文：

LeetCode1-280题汇总，希望对你有点帮助！

LeetCode刷题实战301：删除无效的括号