粉碎糖果

Problem

This question is about implementing a basic elimination algorithm for Candy Crush.

Given a 2D integer array board representing the grid of candy, different positive integers board[i][j] represent different types of candies. A value of board[i][j] = 0 represents that the cell at position \((i, j)\) is empty. The given board represents the state of the game following the player's move. Now, you need to restore the board to a stable state by crushing candies according to the following rules:

1. If three or more candies of the same type are adjacent vertically or horizontally, "crush" them all at the same time - these positions become empty.
2. After crushing all candies simultaneously, if an empty space on the board has candies on top of itself, then these candies will drop until they hit a candy or bottom at the same time. (No new candies will drop outside the top boundary.)
3. After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps.
4. If there does not exist more candies that can be crushed (i.e., the board is stable), then return the current board.

You need to perform the above rules until the board becomes stable, then return the current board.

Example:

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]]

Explanation:

Constraints:

• The length of board will be in the range [3, 50].
• The length of board[i] will be in the range [3, 50].
• Each board[i][j] will initially start as an integer in the range [1, 2000].

Idea

Simulate the game in rounds until the board is stable. Each round has two steps:

1. Mark: scan every row and every column for three equal candies in a line. Mark them by making them negative, so they can still be compared with their neighbors (by absolute value) in the same round. If nothing is marked, the board is stable, so return it.
2. Drop: in each column, use two pointers from the bottom. A read pointer moves up over every cell, and a write pointer moves up only when a positive candy is copied down to it. Then fill every cell above the write pointer with 0.

Time complexity: \(O((mn)^2)\), Space complexity: \(O(1)\), where \(m \times n\) is the size of the board. Each round takes \(O(mn)\), and each round crushes at least 3 candies, so there are at most \(O(mn)\) rounds.

Pseudo Code

def candy_crush(board):
    m, n = len(board), len(board[0])
    while True:
        found = False

        # 1. mark candies to crush by making them negative
        for i in range(m):
            for j in range(n - 2):
                v = abs(board[i][j])
                if v != 0 and v == abs(board[i][j + 1]) == abs(board[i][j + 2]):
                    board[i][j] = board[i][j + 1] = board[i][j + 2] = -v
                    found = True
        for j in range(n):
            for i in range(m - 2):
                v = abs(board[i][j])
                if v != 0 and v == abs(board[i + 1][j]) == abs(board[i + 2][j]):
                    board[i][j] = board[i + 1][j] = board[i + 2][j] = -v
                    found = True

        if not found:
            return board                 # stable

        # 2. drop: move positive candies down in each column
        for j in range(n):
            write = m - 1
            for read in range(m - 1, -1, -1):
                if board[read][j] > 0:
                    board[write][j] = board[read][j]
                    write -= 1
            for i in range(write, -1, -1):
                board[i][j] = 0          # empty cells on top