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)
}
}