aboutsummaryrefslogtreecommitdiff
path: root/flood_fill.py
diff options
context:
space:
mode:
Diffstat (limited to 'flood_fill.py')
-rw-r--r--flood_fill.py37
1 files changed, 37 insertions, 0 deletions
diff --git a/flood_fill.py b/flood_fill.py
new file mode 100644
index 0000000..0f34f29
--- /dev/null
+++ b/flood_fill.py
@@ -0,0 +1,37 @@
+# 733. Flood Fill
+
+"""
+you are given an image represented by an 'm x n' grid of integers 'image',
+where 'image[i][j]' represents the pixel value of the image. you are also
+given three integers 'sr', 'sc', and 'color'. your task is to perform a flood
+fill on the image starting from the pixel 'image[sr][sc]'. return the
+modified image after performing the flood fill
+"""
+
+
+class Solution(object):
+ def floodFill(self, image, sr, sc, color):
+ """
+ :type image: List[List[int]]
+ :type sr: int
+ :type sc: int
+ :type color: int
+ :rtype: List[List[int]]
+ """
+ n, m, old = len(image), len(image[0]), image[sr][sc]
+
+ def dfs(r, c):
+ if (not (0 <= r < n and 0 <= c < m)) or image[r][c] != old:
+ return
+ image[r][c] = color
+ [dfs(r + x, c + y) for (x, y) in ((0, 1), (1, 0), (0, -1), (-1, 0))]
+
+ if old != color:
+ dfs(sr, sc)
+ return image
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.floodFill(image=[[1, 1, 1], [1, 1, 0], [1, 0, 1]], sr=1, sc=1, color=2))
+ print(obj.floodFill(image=[[0, 0, 0], [0, 0, 0]], sr=0, sc=0, color=0))