LeetCode: 723. 粉碎糖果¶

1、题目描述¶

1. 如果有三个及以上水平或者垂直相连的同种糖果，同一时间将它们粉碎，即将这些位置变成空的。
2. 在同时粉碎掉这些糖果之后，如果有一个空的位置上方还有糖果，那么上方的糖果就会下落直到碰到下方的糖果或者底部，这些糖果都是同时下落，也不会有新的糖果从顶部出现并落下来。
3. 通过前两步的操作，可能又会出现可以粉碎的糖果，请继续重复前面的操作。
4. 当不存在可以粉碎的糖果，也就是状态稳定之后，请输出最终的状态。

输入:
board =
[[110,5,112,113,114],[210,211,5,213,214],[310,311,3,313,314],[410,411,412,5,414],[5,1,512,3,3],[610,4,1,613,614],[710,1,2,713,714],[810,1,2,1,1],[1,1,2,2,2],[4,1,4,4,1014]]

[[0,0,0,0,0],[0,0,0,0,0],[0,0,0,0,0],[110,0,0,0,114],[210,0,0,0,214],[310,0,0,113,314],[410,0,0,213,414],[610,211,112,313,614],[710,311,412,613,714],[810,411,512,713,1014]]


• board 数组的行数区间是 [3, 50]。
• board[i] 数组的长度区间（即 board 数组的列数区间）是 [3, 50]。
• 每个 board[i][j] 初始整数范围是 [1, 2000]。

2、解题思路¶

• 模拟消除与降落
• 使用负号进行标记，将所有标记过的清零
• 然后模拟降落操作
class Solution:
def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
row, col = len(board), len(board[0])
flag = False
for i in range(row):
for j in range(col):
if j + 2 < col and abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]) != 0:
board[i][j] = board[i][j + 1] = board[i][j + 2] = -abs(board[i][j])
flag = True
for j in range(col):
for i in range(row):
if i + 2 < row and abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]) != 0:
board[i][j] = board[i + 1][j] = board[i + 2][j] = -abs(board[i][j])
flag = True

for j in range(col):
pos = row - 1
for i in range(row - 1, -1, -1):
if board[i][j] > 0:
board[pos][j] = board[i][j]
pos -= 1

while pos >= 0:
board[pos][j] = 0
pos -= 1
if not flag:
return board
else:
return self.candyCrush(board)