文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè)下標(biāo)從 0 開(kāi)始，大小為 m x n 的二進(jìn)制矩陣 land ，其中 0 表示一單位的森林土地，1 表示一單位的農(nóng)場(chǎng)土地。

為了讓農(nóng)場(chǎng)保持有序，農(nóng)場(chǎng)土地之間以矩形的 農(nóng)場(chǎng)組 的形式存在。
每一個(gè)農(nóng)場(chǎng)組都 僅 包含農(nóng)場(chǎng)土地。且題目保證不會(huì)有兩個(gè)農(nóng)場(chǎng)組相鄰，也就是說(shuō)一個(gè)農(nóng)場(chǎng)組中的任何一塊土地都 不會(huì) 與另一個(gè)農(nóng)場(chǎng)組的任何一塊土地在四個(gè)方向上相鄰。

land 可以用坐標(biāo)系統(tǒng)表示，其中 land 左上角坐標(biāo)為 (0, 0) ，右下角坐標(biāo)為 (m-1, n-1) 。
請(qǐng)你找到所有 農(nóng)場(chǎng)組 最左上角和最右下角的坐標(biāo)。
一個(gè)左上角坐標(biāo)為 (r1, c1) 且右下角坐標(biāo)為 (r2, c2) 的 農(nóng)場(chǎng)組 用長(zhǎng)度為 4 的數(shù)組 [r1, c1, r2, c2] 表示。

請(qǐng)你返回一個(gè)二維數(shù)組，它包含若干個(gè)長(zhǎng)度為 4 的子數(shù)組，每個(gè)子數(shù)組表示 land 中的一個(gè) 農(nóng)場(chǎng)組 。
如果沒(méi)有任何農(nóng)場(chǎng)組，請(qǐng)你返回一個(gè)空數(shù)組?？梢砸?任意順序 返回所有農(nóng)場(chǎng)組。

示例 1：

輸入：land = [[1,0,0],[0,1,1],[0,1,1]] 輸出：[[0,0,0,0],[1,1,2,2]] 解釋： 第一個(gè)農(nóng)場(chǎng)組的左上角為 land[0][0] ，右下角為 land[0][0] 。 第二個(gè)農(nóng)場(chǎng)組的左上角為 land[1][1] ，右下角為 land[2][2] 。

示例 2：

輸入：land = [[1,1],[1,1]] 輸出：[[0,0,1,1]] 解釋： 第一個(gè)農(nóng)場(chǎng)組左上角為 land[0][0] ，右下角為 land[1][1] 。

示例 3：

輸入：land = [[0]] 輸出：[] 解釋： 沒(méi)有任何農(nóng)場(chǎng)組。提示： m == land.length n == land[i].length 1 <= m, n <= 300 land 只包含 0 和 1 。 農(nóng)場(chǎng)組都是 矩形 的形狀。

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/find-all-groups-of-farmland
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• BFS，廣度優(yōu)先搜索，DFS也可以

class Solution { public:vector<vector<int>> findFarmland(vector<vector<int>>& land) {int m = land.size(), n = land[0].size(), k = 300;queue<int> q;vector<vector<int>> ans;vector<vector<int>> dir = {{0,1},{1,0},{-1,0},{0,-1}};for(int i = 0; i < m; ++i){for(int j = 0; j < n; ++j){if(land[i][j] == 1){vector<int> pos = {i,j,i,j};q.push(i*k+j);land[i][j] = 0; // 訪(fǎng)問(wèn)過(guò)了while(!q.empty()){int num = q.front();int x = num/k;int y = num%k;q.pop();pos[0] = min(pos[0], x);pos[1] = min(pos[1], y);pos[2] = max(pos[2], x);pos[3] = max(pos[3], y);for(int d = 0; d < 4; ++d){int nx = x + dir[d][0];int ny = y + dir[d][1];if(nx>=0 && nx < m && ny>=0 && ny<n && land[nx][ny]){land[nx][ny] = 0;q.push(nx*k+ny);}}}ans.push_back(pos);}}}return ans;} };

156 ms 60.9 MB C++

---

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

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 1992. 找到所有的农场组（BFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。