LeetCode 筆記 - 733. Flood Fill

題目在此 733. Flood Fill

image 14

給一張圖,給你一個點座標跟新顏色,請你將新顏色取代舊顏色

解題思維

根據題目給的座標下去做一次 Depth First Search 即可

程式碼

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

也許你也會想看看