Re: [閒聊] 每日leetcode已回收
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)
}
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.203.208 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713602338.A.747.html
→
04/20 16:41,
1年前
, 1F
04/20 16:41, 1F
推
04/20 16:44,
1年前
, 2F
04/20 16:44, 2F
推
04/20 16:45,
1年前
, 3F
04/20 16:45, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 138 之 1548 篇)：