-
Notifications
You must be signed in to change notification settings - Fork 0
/
flood-fill.py
31 lines (28 loc) · 1.04 KB
/
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
29
30
31
# https://leetcode.com/problems/flood-fill/
from typing import List
class Solution:
def floodFill(self, image: List[List[int]], sr: int, sc: int, color: int) -> List[List[int]]:
if image[sr][sc] == color:
return image
result = []
rows = len(image)
cols = len(image[0])
for i in range(rows):
row = []
for j in range(cols):
row.append(image[i][j])
result.append(row)
base_color = image[sr][sc]
queue = [(sr, sc)]
while queue:
i, j = queue.pop()
result[i][j] = color
if i - 1 >= 0 and result[i - 1][j] == base_color:
queue.append((i - 1, j))
if j + 1 < cols and result[i][j + 1] == base_color:
queue.append((i, j + 1))
if i + 1 < rows and result[i + 1][j] == base_color:
queue.append((i + 1, j))
if j - 1 >= 0 and result[i][j - 1] == base_color:
queue.append((i, j - 1))
return result