forked from kamyu104/LeetCode-Solutions
-
Notifications
You must be signed in to change notification settings - Fork 0
/
flood-fill.py
29 lines (24 loc) · 810 Bytes
/
flood-fill.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Time: O(m * n)
# Space: O(m * n)
class Solution(object):
def floodFill(self, image, sr, sc, newColor):
"""
:type image: List[List[int]]
:type sr: int
:type sc: int
:type newColor: int
:rtype: List[List[int]]
"""
directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
def dfs(image, r, c, newColor, color):
if not (0 <= r < len(image) and \
0 <= c < len(image[0]) and \
image[r][c] == color):
return
image[r][c] = newColor
for d in directions:
dfs(image, r+d[0], c+d[1], newColor, color)
color = image[sr][sc]
if color == newColor: return image
dfs(image, sr, sc, newColor, color)
return image