class Solution:
def crush(self, board):
visited = set()
rows = len(board)
cols = len(board[0])
def bfs(board, x, y, i, j, count):
directions = [(1,0), (-1,0), (0,1), (0,-1)]
if board[x][y] == board[i][j]:
if count >= 3:
board[x][y] = 0
for direction in directions:
a = x + direction[0]
b = y + direction[1]
if a >= 0 and a < rows and b >= 0 and b < cols and (a,b) not in visited:
bfs(board, a, b, i, j, count+1)
for i in range(rows):
for j in range(cols):
if (i,j) not in visited:
bfs(board, i, j, i, j, 1)
def move(self, board):
rows = len(board)
cols = len(board[0])
board_modified = False
for col in range(cols):
next_nonzero = rows-1
for i in range(next_nonzero, -1, -1):
if board[i][col] != 0:
board[i][col], board[next_nonzero][col] = board[next_nonzero][col], board[i][col]
next_nonzero -= 1
if next_nonzero > i:
board_modified = True
return board_modified
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
board_modified = True
while board_modified:
self.crush(board)
board_modified = self.move(board)
return board
civic dirge