※ 引述《JIWP (神楽めあ的钱包)》之铭言：
: 1992. Find All Groups of Farmland
: 有一块m*n的土地
: 1代表农地、0代表森林
: 且农地根森林一定是矩形
: 请找出所有农地的左上座标和右上座标
: 思路 :
: 农地右下的座标其x、y一定是整块农地里最大的值
: 从上到下、从左到右去遍历整块土地
: 当遇到1就进到dfs函式
: dfs函式里面就是把land[i][j]变成0
: 并且不断找最大的x,y
: 这样就可以找到答案了
: 然后不用4个方向都去找
: 只要找右边、下面就可以遍历完整个农地了
: golang code:
: var r, c int
: func findFarmland(land [][]int) [][]int {
: r = len(land)
: c = len(land[0])
: ans := make([][]int, 0)
: for i := 0; i < r; i++ {
: for j := 0; j < c; j++ {
: if land[i][j] == 1 {
: temp := []int{i, j, 0, 0}
: find(&land, i, j, &temp)
: ans = append(ans, temp)
: }
: }
: }
: return ans
: }
: func find(land *[][]int, i, j int, temp *[]int) {
: if i < r && j < c && (*land)[i][j] == 1 {
: (*land)[i][j] = 0
: (*temp)[2] = max((*temp)[2], i)
: (*temp)[3] = max((*temp)[3], j)
: find(land, i, j+1, temp)
: find(land, i+1, j, temp)
: }
: }
思路:
遍历整个list 遇到1就dfs 因为右下角必然是整个矩形的最大值
用max()找到最大值就可以得到答案
Python Code:
class Solution:
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
def dfs(x,y):
dx = [1,0]
dy = [0,1]
for i in range(2):
new_x = x + dx[i]
new_y = y + dy[i]
if new_x>=0 and new_x<m and new_y>=0 and new_y<n and
land[new_y][new_x] == 1:
land[new_y][new_x] = 0
result[-1][2] = max(result[-1][2],new_y)
result[-1][3] = max(result[-1][3],new_x)
dfs(new_x,new_y)
result = []
n,m = len(land),len(land[0])
for i in range(n):
for j in range(m):
if land[i][j] == 1:
result.append([i,j,i,j])
land[i][j] = 0
dfs(j,i)
return result