Сложность: medium
Этот вопрос касается реализации базового алгоритма исключения для Candy Crush. Дан целочисленный массив board размером m x n, представляющий сетку конфет, где board[i][j] представляет тип конфеты. Значение board[i][j] == 0 означает, что ячейка пуста. Данная доска представляет собой состояние игры после хода игрока. Теперь необходимо вернуть доску в стабильное состояние, раздавив конфеты по следующим правилам: если три или более конфет одного типа находятся рядом по вертикали или горизонтали, раздавите их все одновременно - эти позиции станут пустыми. После одновременного раздавливания всех конфет, если на пустом месте доски есть конфеты, расположенные сверху, то эти конфеты будут падать, пока не ударятся о конфету или дно одновременно. Новые конфеты не будут падать за верхнюю границу. После выполнения описанных выше действий может остаться больше конфет, которые можно раздавить. Если конфет, которые можно раздавить, больше не существует (т. е. доска стабильна), верните текущую доску. Выполняйте описанные выше правила, пока доска не станет стабильной, затем верните стабильную доску.
Пример:
Input: 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]]
Output: [[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]]
👨💻 Алгоритм:
1⃣Найдите все группы из трех или более одинаковых конфет, как в горизонтальном, так и в вертикальном направлениях, и отметьте их для удаления.
2⃣Удалите отмеченные конфеты, установив их значение в 0.
3⃣Переместите конфеты вниз, чтобы заполнить пустые ячейки, и повторите процесс, пока не останется групп конфет для удаления.
😎 Решение:
def candyCrush(board):
m, n = len(board), len(board[0])
stable = False
while not stable:
stable = True
crush = [[False] * n for _ in range(m)]
for i in range(m):
for j in range(n - 2):
if abs(board[i][j]) == abs(board[i][j + 1]) == abs(board[i][j + 2]) != 0:
stable = False
crush[i][j] = crush[i][j + 1] = crush[i][j + 2] = True
for i in range(m - 2):
for j in range(n):
if abs(board[i][j]) == abs(board[i + 1][j]) == abs(board[i + 2][j]) != 0:
stable = False
crush[i][j] = crush[i + 1][j] = crush[i + 2][j] = True
for i in range(m):
for j in range(n):
if crush[i][j]:
board[i][j] = 0
for j in range(n):
idx = m - 1
for i in range(m - 1, -1, -1):
if board[i][j] != 0:
board[idx][j] = board[i][j]
idx -= 1
for i in range(idx, -1, -1):
board[i][j] = 0
return board
Ставь 👍 и забирай 📚 Базу знаний