1992. Find All Groups of Farmland

Description

You are given a 0-indexed m x n binary matrix land where a 0 represents a hectare of forested land and a 1 represents a hectare of farmland.

To keep the land organized, there are designated rectangular areas of hectares that consist entirely of farmland. These rectangular areas are called groups. No two groups are adjacent, meaning farmland in one group is not four-directionally adjacent to another farmland in a different group.

land can be represented by a coordinate system where the top left corner of land is (0, 0) and the bottom right corner of land is (m-1, n-1). Find the coordinates of the top left and bottom right corner of each group of farmland. A group of farmland with a top left corner at (r1, c1) and a bottom right corner at (r2, c2) is represented by the 4-length array [r1, c1, r2, c2].

Return a 2D array containing the 4-length arrays described above for each group of farmland in land. If there are no groups of farmland, return an empty array. You may return the answer in any order.

Example

Example1

Input: land = [[1,0,0],[0,1,1],[0,1,1]]
Output: [[0,0,0,0],[1,1,2,2]]
Explanation:
The first group has a top left corner at land[0][0] and a bottom right corner at land[0][0].
The second group has a top left corner at land[1][1] and a bottom right corner at land[2][2].

Example2

Input: land = [[1,1],[1,1]]
Output: [[0,0,1,1]]
Explanation:
The first group has a top left corner at land[0][0] and a bottom right corner at land[1][1].

Example3

Input: land = [[0]]
Output: []
Explanation:
There are no groups of farmland.

Constraints:

• m == land.length
• n == land[i].length
• 1 <= m, n <= 300
• land consists of only 0's and 1's.
• Groups of farmland are rectangular in shape.

思路

使用 for loop 遍歷整個 land，若是遇到 1 便進入 dfs，此 dfs 的功能有將走過得地方清為 0 與將比 tmp (每個小正方形的陣列) 的最右下角（最大）的 row/col 更新。
因為題目限定都是正方形，所以 dfs 可以限定在往右跟往下走，減少 dfs 成本。

C++

class Solution {
public:
    void dfs(vector<vector<int>>& land, int row, int col, int maxr, int maxc,
             vector<int>& tmp) {
        if (row < 0 || col < 0 || row >= maxr || col >= maxc ||
            land[row][col] == 0)
            return;

        land[row][col] = 0;
        if (row > tmp[2])
            tmp[2] = row;
        if (col > tmp[3])
            tmp[3] = col;

        // dfs(land, row-1, col, maxr, maxc, tmp);
        dfs(land, row + 1, col, maxr, maxc, tmp);
        // dfs(land, row, col-1, maxr, maxc, tmp);
        dfs(land, row, col + 1, maxr, maxc, tmp);
    }
    vector<vector<int>> findFarmland(vector<vector<int>>& land) {
        int m = land.size();
        int n = land[0].size();
        vector<vector<int>> ret;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 1) {
                    vector<int> tmp = {i, j, i, j};
                    dfs(land, i, j, m, n, tmp);
                    ret.push_back(tmp);
                }
            }
        }
        return ret;
    }
};