-
Notifications
You must be signed in to change notification settings - Fork 0
/
723.py
92 lines (77 loc) · 2.84 KB
/
723.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
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
self.R = len(board)
self.C = len(board[0])
board_start = board
while True:
marked_board = self.mark_crush(board_start)
crushed_board = self.crush(marked_board)
if self.is_equal(board_start, crushed_board):
return crushed_board
else:
board_start = crushed_board
def mark_crush(self, board):
marked_board = self.copy_board(board)
# find same candies horizontally
for r in range(self.R):
start = 0
end = 0
streak = 0
while end < self.C:
if board[r][start] == board[r][end]:
end += 1
streak += 1
else:
if streak >= 3:
for i in range(start, end):
if i < self.C:
marked_board[r][i] = 0
start = end
streak = 0
if streak >= 3:
for i in range(start, self.C):
marked_board[r][i] = 0
# find same candies vertically
for c in range(self.C):
start = 0
end = 0
streak = 0
while end < self.R:
if board[start][c] == board[end][c]:
end += 1
streak += 1
else:
if streak >= 3:
for i in range(start, end):
if i < self.R:
marked_board[i][c] = 0
start = end
streak = 0
if streak >= 3:
for i in range(start, self.R):
marked_board[i][c] = 0
return marked_board
def crush(self, board):
new_board = self.get_empty_board()
for c in range(self.C):
j = self.R-1
for i in range(self.R-1, -1, -1):
if board[i][c] == 0:
continue
new_board[j][c] = board[i][c]
j -= 1
return new_board
def get_empty_board(self):
return [[0 for _ in range(self.C)] for _ in range(self.R)]
def copy_board(self, board):
empty_board = self.get_empty_board()
for r in range(self.R):
for c in range(self.C):
empty_board[r][c] = board[r][c]
return empty_board
def is_equal(self, a, b):
for r in range(self.R):
for c in range(self.C):
if a[r][c] != b[r][c]:
return False
return True