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