Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/find-all-groups-of-farmland/description
1992. Find All Groups of Farmland
給你一個包含0和1的二維陣列，0表示上面是叢林，1表示上面是農地，如果農地的上下
左右相鄰他們就是同一塊地，求出每一塊地的"左上角"和"右下角"座標。
思路:
1.從左上遍歷到右下，如果當前點為1表示發現一塊農地，以該點為中心dfs所有相鄰
的1把他標記成已走過，過程中對右下角的座標的y和x不斷取max。
2.返回結果集。
py code:
-------------------------------------------------------------
class Solution:
def findFarmland(self, land: List[List[int]]) -> List[List[int]]:
res = []
m, n = len(land), len(land[0])
def dfs(y: int, x: int):
if y < 0 or y == m or x < 0 or x == n or land[y][x] != 1:
return
farm = res[-1]
farm[2] = max(farm[2], y)
farm[3] = max(farm[3], x)
land[y][x] = 0
dfs(y + 1, x)
dfs(y - 1, x)
dfs(y, x + 1)
dfs(y, x - 1)
for i in range(m):
for j in range(n):
if land[i][j] == 1:
res.append([i, j, i, j])
dfs(i, j)
return res
-------------------------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1713600438.A.C17.html
推
04/20 16:16,
1年前
, 1F
04/20 16:16, 1F
討論串 (同標題文章)
完整討論串 (本文為第 137 之 1548 篇)：