文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

圖片在計算機處理中往往是使用二維矩陣來表示的。

假設，這里我們用的是一張黑白的圖片，那么 0 代表白色像素，1 代表黑色像素。

其中黑色的像素他們相互連接，也就是說，圖片中只會有一片連在一塊兒的黑色像素（像素點是水平或豎直方向連接的）。

那么，給出某一個黑色像素點 (x, y) 的位置，你是否可以找出包含全部黑色像素的最小矩形（與坐標軸對齊）的面積呢？

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/smallest-rectangle-enclosing-black-pixels
著作權歸領扣網絡所有。商業(yè)轉載請聯系官方授權，非商業(yè)轉載請注明出處。

2. 解題

• 簡單的模板題，BFS、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);} };

84 ms 14 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 302. 包含全部黑色像素的最小矩形（BFS）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。