# 1992. Find All Groups of Farmland
###### tags: `Leetcode` `Medium` `DFS`
Link: https://leetcode.com/problems/find-all-groups-of-farmland/description/
## 思路
[参考](https://leetcode.com/problems/find-all-groups-of-farmland/solutions/1451820/mark-left-side/)
### 思路一 O(2mn)
遍历land array 当发现一个位置值是1的时候 说明发现一个farmland 遍历整个farmland 并把相应位置设置成0 防止重复遍历 最后把当下farmland加进答案
### 思路二 O(mn)
遍历land array 当发现一个位置值是1的时候 说明发现一个farmland
接下来首先找到这个farmland占了几个column ```col```
然后我们把这个land的左边界的每个位置都标成```col+1``` 表示下次遍历到这里时可以直接跳过```col```个格子
如果发现一个位置值是大于1的话 说明这里已经遍历过 直接跳过就好
要注意的是左边标的是```col+1``` 而不是```col``` 这样即使只占了一个column我们也会知道我们遍历过这里了 从而跳过一个格子 避免重复
## Code
### 思路一

class Solution {
    public int[][] findFarmland(int[][] land) {
        int m = land.length, n = land[0].length;
        List<int[]> res = new ArrayList<>();
        for(int i=0; i<m; i++){
            for(int j=0; j<n; j++){
                if(land[i][j]==1){
                    int ii = i, jj = j;
                    for(ii=i; ii<m && land[ii][j]==1; ii++){
                        for(jj=j; jj<n && land[ii][jj]==1; jj++){
                            land[ii][jj]=0;
                        }
                    }
                    res.add(new int[]{i, j, ii-1, jj-1});
                }
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

### 思路二

class Solution:
    def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
        ans = []
        m, n = len(land), len(land[0])
        i, j = 0, 0
        while i<m:
            j = 0
            while j<n:
                if land[i][j]==1:
                    ii, jj = i, j
                    while jj<n and land[i][jj]==1: jj += 1
                    while ii<m and land[ii][j]==1:
                        land[ii][j] = jj-j+1
                        ii += 1
                    ans.append([i, j, ii-1, jj-1])
                if land[i][j]>1:
                    j += land[i][j]-1
                j += 1
            i += 1
        return ans