aboutsummaryrefslogtreecommitdiff
path: root/find_group_farmland.py
diff options
context:
space:
mode:
authorjack <[email protected]>2024-06-14 13:13:15 -0600
committerjack <[email protected]>2024-06-14 13:13:15 -0600
commitd343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa (patch)
tree96df922dae2a5073d9a50ea70c7aae6aa37e3ebe /find_group_farmland.py
downloadleetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.tar.gz
leetcode-d343a3b18dbaca9297d4f7b2280c4a16f0a5c8aa.zip
initial
Diffstat (limited to 'find_group_farmland.py')
-rw-r--r--find_group_farmland.py59
1 files changed, 59 insertions, 0 deletions
diff --git a/find_group_farmland.py b/find_group_farmland.py
new file mode 100644
index 0000000..e52f31f
--- /dev/null
+++ b/find_group_farmland.py
@@ -0,0 +1,59 @@
+# 1992. Find All Groups of Farmland
+
+"""
+given a 0-indexed 'm n' binary matrix 'land' where a 0 represents a hectare
+of forested land and a 1 represents a hectare of farmland. to keep the land
+organised, there are designated rectangular areas of hectares that consist
+entirely of farmland. these rectangular areas are called groups. no two
+groups are adjacent, meaning farmland in one group is not four directionally
+adjacent to another farmland in another group. return a 2d array containing
+the 4 length arrays described above for each group o farmland in 'land'.
+"""
+
+
+class Solution(object):
+ def findFarmland(self, land):
+ """
+ :type land: List[List[int]]
+ :rtype: List[List[int]]
+ """
+
+ def dfs(x, y):
+ stack = [(x, y)]
+ min_row, min_col = x, y
+ max_row, max_col = x, y
+ visited.add((x, y))
+ while stack:
+ cur_x, cur_y = stack.pop()
+ for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
+ nx, ny = cur_x + dx, cur_y + dy
+ if (
+ 0 <= nx < rows
+ and 0 <= ny < cols
+ and (nx, ny) not in visited
+ and land[nx][ny] == 1
+ ):
+ visited.add((nx, ny))
+ stack.append((nx, ny))
+ min_row = min(min_row, nx)
+ min_col = min(min_col, ny)
+ max_row = max(max_row, nx)
+ max_col = max(max_col, ny)
+ return (min_row, min_col, max_row, max_col)
+
+ rows, cols = len(land), len(land[0])
+ visited = set()
+ ans = []
+ for i in range(rows):
+ for j in range(cols):
+ if land[i][j] == 1 and (i, j) not in visited:
+ min_row, min_col, max_row, max_col = dfs(i, j)
+ ans.append([min_row, min_col, max_row, max_col])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findFarmland(land=[[1, 0, 0], [0, 1, 1], [0, 1, 1]]))
+ print(obj.findFarmland(land=[[1, 1], [1, 1]]))
+ print(obj.findFarmland(land=[[0]]))