-
Notifications
You must be signed in to change notification settings - Fork 3
/
week4_jiaqiwu_flood.py
141 lines (116 loc) · 3.63 KB
/
week4_jiaqiwu_flood.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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
from typing import List
directions = [[-1, 0], [0, -1], [0, 1], [1, 0]]
def flood_fill(input_board: List[str], old: str, new: str, x: int, y: int) -> List[str]:
"""Returns board with old values replaced with new values
through flood filling starting from the coordinates x, y
Args:
input_board (List[str])
old (str): Value to be replaced
new (str): Value that replaces the old
x (int): X-coordinate of the flood start point
y (int): Y-coordinate of the flood start point
Returns:
List[str]: Modified board
"""
# Implement your code here.
row = len(input_board)
col = len(input_board[0])
# ensure the length of each row is same
for r in range(1, row):
assert len(board[r]) == len(board[0])
board_arr = []
for line in input_board:
board_arr.append(list(line))
if (not (0 <= x < row and 0 <= y < col)) or board_arr[x][y] != old:
return input_board
dfs(board_arr, x, y, row, col, old, new)
res = []
for line in board_arr:
res.append("".join(line))
return res
def dfs(board_arr: List[List[str]], x: int, y: int, row: int, col: int, old: str, new: str):
"""
Args:
board_arr (List[List[str]])
x (int): X-coordinate of the flood current point
y (int): Y-coordinate of the flood current point
row (int): the number of row
col (int): the umber of column
old (str): Value to be replaced
new (str): Value that replaces the old
Returns:
No returns
"""
board_arr[x][y] = new
for direct in directions:
x_ = x + direct[0]
y_ = y + direct[1]
if 0 <= x_ < row and 0 <= y_ < col and board_arr[x_][y_] == old:
dfs(board_arr, x_, y_, row, col, old, new)
board = [
"......................",
"......##########......",
"......#........#......",
"......#........#......",
"......#........#####..",
"....###............#..",
"....#............###..",
"....##############....",
]
modified_board = flood_fill(input_board=board, old=".", new="~", x=5, y=12)
for a in modified_board:
print(a)
expected_output = [
"......................",
"......##########......",
"......#~~~~~~~~#......",
"......#~~~~~~~~#......",
"......#~~~~~~~~#####..",
"....###~~~~~~~~~~~~#..",
"....#~~~~~~~~~~~~###..",
"....##############....",
]
# Expected output:
# ......................
# ......##########......
# ......#~~~~~~~~#......
# ......#~~~~~~~~#......
# ......#~~~~~~~~#####..
# ....###~~~~~~~~~~~~#..
# ....#~~~~~~~~~~~~###..
# ....##############....
print()
board_2 = [
"...........#..........",
"......####...###......",
"......#........#......",
"......#........#......",
"......#........#####..",
"....###............#..",
"....#............###..",
"....##############....",
]
expected_output_2 = [
"~~~~~~~~~~~#~~~~~~~~~~",
"~~~~~~####~~~###~~~~~~",
"~~~~~~#~~~~~~~~#~~~~~~",
"~~~~~~#~~~~~~~~#~~~~~~",
"~~~~~~#~~~~~~~~#####~~",
"~~~~###~~~~~~~~~~~~#~~",
"~~~~#~~~~~~~~~~~~###~~",
"~~~~##############~~~~",
]
# Expected output:
# ~~~~~~~~~~~#~~~~~~~~~~
# ~~~~~~####~~~###~~~~~~
# ~~~~~~#~~~~~~~~#~~~~~~
# ~~~~~~#~~~~~~~~#~~~~~~
# ~~~~~~#~~~~~~~~#####~~
# ~~~~###~~~~~~~~~~~~#~~
# ~~~~#~~~~~~~~~~~~###~~
# ~~~~##############~~~~
modified_board_2 = flood_fill(input_board=board_2, old=".", new="~", x=0, y=0)
for a in modified_board_2:
print(a)
assert flood_fill(input_board=board, old=".", new="~", x=5, y=12) == expected_output
assert flood_fill(input_board=board_2, old=".", new="~", x=0, y=0) == expected_output_2