723. Candy Crush

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

Given an m x n integer array board representing the grid of candy where board[i][j] represents the type of candy. A value of board[i][j] == 0 represents that the cell 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:

• 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.
• 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.
• After the above steps, there may exist more candies that can be crushed. If so, you need to repeat the above steps.
• 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 stable board.

 

Example 1:

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

Example 2:

Input: board = [[1,3,5,5,2],[3,4,3,3,1],[3,2,4,5,2],[2,4,4,5,5],[1,4,4,1,1]]
Output: [[1,3,0,0,0],[3,4,0,5,2],[3,2,0,3,1],[2,4,0,5,2],[1,4,3,1,1]]

Solution

Solution

---

Overview

The game process may be somewhat complex. Let's start by understanding the game steps and finding the corresponding actions for each step. We can divide this game into several (potentially repeating) steps:

• find
• crush
• drop

Find stands for finding all crushable candies, crush represents the elimination of adjacent candies, while drop involves rearranging the candies and making the ones above fall down. We mention that these steps are potentially repeated because after a drop, the rearranged candies may form new groups of candies to be crushed, requiring us to repeat the steps until we can no longer find a group of crushable candies.

---

Approach 1: Separate Steps: Find, Crush, Drop

Intuition

Starting from the first step: find and mark cells in the current board to be crushed. One simple approach is to check if three candies in the same row or column centered around a particular cell (r, c), are the same. That is, either board[r][c] = board[r - 1][c] = board[r + 1][c], or board[r][c] = board[r][c - 1] = board[r][c + 1]. If certain candies meet these conditions and qualify as crushable candies, we can store their positions.

After iterating through all the cells, if no new candies to be crushed are found, it indicates that the game is over. Otherwise, we continue with crushing candies. We modify the values of the stored candy positions to 0, indicating that they have been eliminated. At this point, we have completed the second step of the game.

In the third step, we need to make the candies above fall down until they hit the bottom or another candy.

During this process, the candies can only fall downwards, meaning that each column of the board is independent. It would be helpful to discuss them separately for easier computation.

For each column, we traverse from bottom to top. Throughout this process, we keep track of the position of the lowest 0 value. If the current cell is not 0, it will eventually fall to this lowest 0 position. Therefore, we swap its position with the position of the lowest 0, and raise the position of the lowest 0 by 1.

In summary, through the aforementioned three steps, we obtain a new board.

Next, we need to continue checking if there are any crushable candies in the new grid. If we discover new crushable candies, we repeat these steps again.

Finally, when no group of crushable candies can be found, it indicates that the game is over.

Algorithm

1. Define find() to find all crushable candies:

   • Initialize an empty set crushed_set.
   • Iterate over each candy (r, c):
     • If board[r][c] = 0, continue.
     • If board[r][c] = board[r + 1][c] = board[r - 1][c], add (r, c), (r + 1, c) and (r - 1, c) to the set. If board[r][c] = board[r][c + 1] = board[r][c - 1], add (r, c), (r, c + 1) and (r, c - 1) to the set.
   • Return crushed_set.

2. Define crush(crushed_set) to mark all crushable candies:

   • Iterate over every candy (r, c) in crushed_set and set board[r][c] = 0.

3. Define drop() to rearrange the candies' new positions based on the rules:

   • Iterate over each column c.
   • For each column, set lowest_zero as -1 since there is no lowest zero yet.
   • Iterate candies (r, c) from bottom to top, for each candy board[r][c]. If board[r][c] is zero, update lowest_zero as lowest_zero = max(lowest_zero, r). If board[r][c] is non-zero and lowest_zero is not -1, then we swap board[r][c] with board[lowest_zero][c] and decrement lowest_zero by 1.

4. While find() returns an non-empty set crushed_set:

   • Perform crush(crushed_set).
   • Perform drop().

5. Return board when the while loop is complete.

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        m, n = len(board), len(board[0])

        def find():
            crushed_set = set()

            # Check vertically adjacent candies 
            for r in range(1, m - 1):
                for c in range(n):
                    if board[r][c] == 0:
                        continue
                    if board[r][c] == board[r - 1][c] == board[r + 1][c]: 
                        crushed_set.add((r, c))
                        crushed_set.add((r - 1, c))
                        crushed_set.add((r + 1, c))

            # Check horizontally adjacent candies 
            for r in range(m):
                for c in range(1, n - 1):
                    if board[r][c] == 0:
                        continue
                    if board[r][c] == board[r][c - 1] == board[r][c + 1]:
                        crushed_set.add((r, c))
                        crushed_set.add((r, c - 1))
                        crushed_set.add((r, c + 1))
            return crushed_set
        
        # Set the value of each candies to be crushed as 0
        def crush(crushed_set):
            for (r, c) in crushed_set:
                board[r][c] = 0
        
        def drop():
            for c in range(n):
                lowest_zero = -1
                for r in range(m - 1, -1, -1):
                    if board[r][c] == 0:
                        lowest_zero = max(lowest_zero, r)
                    elif lowest_zero >= 0:
                        board[r][c], board[lowest_zero][c] = board[lowest_zero][c], board[r][c]
                        lowest_zero -= 1

        crushed_set = find()
        while crushed_set:
            crush(crushed_set)
            drop()
            crushed_set = find()

        return board