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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
| class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
origin_color = image[sr][sc]
if origin_color == newColor:
return image
size_y = len(image)
size_x = len(image[0])
def get_neighbors(y, x):
offset = [-1, 1]
result = []
for o in offset:
new_y = y + o
if not 0 <= new_y < size_y:
continue
if image[new_y][x] != origin_color:
continue
result.append((new_y, x))
for o in offset:
new_x = x + o
if not 0 <= new_x < size_x:
continue
if image[y][new_x] != origin_color:
continue
result.append((y, new_x))
return result
def dfs(origin_color, new_color, y, x):
if image[y][x] != origin_color:
return
image[y][x] = new_color
neighbors = get_neighbors(y, x)
for n_y, n_x in neighbors:
dfs(origin_color, new_color, n_y, n_x)
dfs(origin_color, newColor, sr, sc)
return image
|
