Problem Statement
The task requires simulating a game similar to "Candy Crush" where candies are crushed according to specific rules and the board gets updated automatically. Your job is to write a function that takes an m x n integer array board, which presents a grid of candy where each entry board[i][j] indicates the type of candy present. Here, a value of board[i][j] == 0 suggests that the cell is empty.
After each move, your function must update the board by crushing the candies when three or more candies of the same type line up either vertically or horizontally. The crushed candies leave an empty space (0). Subsequently, any candies above an empty cell will drop down to fill the space, adhering strictly to gravity (candies above fall straight down). These steps might reveal new opportunities for crushing, demanding a repeat of the crushing process until no more crushes are possible, signifying a stable board. Your function must repeatedly apply these rules and return the stable state of the board.
Examples
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]]
Constraints
m == board.lengthn == board[i].length3 <= m, n <= 501 <= board[i][j] <= 2000
Approach and Intuition
Scanning for Crushes:
- Traverse the board to identify any row or column with three or more consecutive candies of the same type. This step involves scanning each row and column in the grid.
- Mark these candies for crushing (possibly by setting them temporarily to a special value or directly to
0).
Crushing Process:
- Once the crushable candies are identified, change their values to
0to indicate that they've been crushed.
- Once the crushable candies are identified, change their values to
Gravity Implementation:
- For each column, starting from the bottom-most row, pull down non-empty candies to fill the gaps created by crushed candies. This step would move the values downwards filling the zeros and leaving the top cells empty or zeroed out if necessary.
Repeat the Process:
- After the gravity step, there might be new alignments of candies which can be crushed. The entire process needs to be repeated: scanning for crushes, crushing candies, and applying gravity until no more candies can be crushed.
This repeated crushing and filling process ensures that the board reaches a stable state with no crushable candies left. The goal is to keep a time-efficient tracking of crushable spots and executing gravity correctly, which determines the efficiency of the simulation.
Given the constraints of the board size (3 to 50 in both dimensions), a careful yet straightforward implementation of these steps is feasible without hitting performance bottlenecks. Thus, ensuring that the program repeatedly processes the board until stability without excessive computations is crucial.
Solutions
- Java
- Python
class Solution {
int rows, cols;
boolean checkAndDestroy(int[][] grid) {
boolean isDone = true;
// Vertical alignment checking
for (int row = 1; row < rows - 1; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 0) {
continue;
}
if (Math.abs(grid[row][col]) == Math.abs(grid[row - 1][col]) && Math.abs(grid[row][col]) == Math.abs(grid[row + 1][col])) {
grid[row][col] = -Math.abs(grid[row][col]);
grid[row - 1][col] = -Math.abs(grid[row - 1][col]);
grid[row + 1][col] = -Math.abs(grid[row + 1][col]);
isDone = false;
}
}
}
// Horizontal alignment checking
for (int row = 0; row < rows; row++) {
for (int col = 1; col < cols - 1; col++) {
if (grid[row][col] == 0) {
continue;
}
if (Math.abs(grid[row][col]) == Math.abs(grid[row][col - 1]) && Math.abs(grid[row][col]) == Math.abs(grid[row][col + 1])) {
grid[row][col] = -Math.abs(grid[row][col]);
grid[row][col - 1] = -Math.abs(grid[row][col - 1]);
grid[row][col + 1] = -Math.abs(grid[row][col + 1]);
isDone = false;
}
}
}
// Reset cells to be eliminated
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] < 0) {
grid[row][col] = 0;
}
}
}
return isDone;
}
void fall(int[][] grid) {
for (int col = 0; col < cols; col++) {
int sink = -1;
// Process each column from bottom to top for falling
for (int row = rows - 1; row >= 0; row--) {
if (grid[row][col] == 0) {
sink = Math.max(sink, row);
} else if (sink >= 0) {
// Swap
grid[sink][col] = grid[row][col];
grid[row][col] = 0;
sink--;
}
}
}
}
public int[][] processGame(int[][] grid) {
rows = grid.length;
cols = grid[0].length;
// Repeat until no more combinations
while (!checkAndDestroy(grid)) {
fall(grid);
}
return grid;
}
}
This Java code provides a simulation of the "Candy Crush" game mechanics where groups of three or more same valued cells vertically or horizontally get destroyed, and cells above the destroyed ones fall down to fill their places. The implemented methods work on a provided 2-dimensional grid representing the game board.
Initialization and Main Processing Method: The
rowsandcolsare initially set from the given grid dimensions. The main functionprocessGame()initiates the game processing within a loop, continually checking for and destroying aligned groups of candies usingcheckAndDestroy()and allowing candies to fall down with thefall()method. Processing repeats until no further crushable groups are detected.Detection and Destruction of Candy Groups: In
checkAndDestroy(), the grid is first scanned for groups of three or more candies aligned vertically or horizontally. Detected groups are marked for destruction by negating their values, marking them temporarily while checking other possibilities without alteration of ongoing checks. Subsequently, all marked candies are set to zero, representing their removal from the board.Candy Falling Logic: The
fall()method manipulates the grid columns individually to emulate the falling effect. Each empty spot (zero value) causes the above candies to fall into its place with any candy effectively 'sinking' down to the lowest available empty position in its column.
By handling cyclic checks and updates to the grid until no further actions are possible, the game mimics the continuous crush and fall actions characteristic of Candy Crush. The output is the processed grid after all possible crushes have been performed and no further moves are left.
class Game:
def processBoard(self, grid: List[List[int]]) -> List[List[int]]:
rows, cols = len(grid), len(grid[0])
def check_crush():
stable = True
# Vertical checking
for row in range(1, rows - 1):
for col in range(cols):
if grid[row][col] == 0:
continue
if abs(grid[row][col]) == abs(grid[row - 1][col]) == abs(grid[row + 1][col]):
grid[row][col] = -abs(grid[row][col])
grid[row - 1][col] = -abs(grid[row - 1][col])
grid[row + 1][col] = -abs(grid[row + 1][col])
stable = False
# Horizontal checking
for row in range(rows):
for col in range(1, cols - 1):
if grid[row][col] == 0:
continue
if abs(grid[row][col]) == abs(grid[row][col - 1]) == abs(grid[row][col + 1]):
grid[row][col] = -abs(grid[row][col])
grid[row][col - 1] = -abs(grid[row][col - 1])
grid[row][col + 1] = -abs(grid[row][col + 1])
stable = False
# Zero out crushed candies
for row in range(rows):
for col in range(cols):
if grid[row][col] < 0:
grid[row][col] = 0
return stable
def gravity():
for col in range(cols):
new_place = -1
# Process gravity within a column
for row in range(rows - 1, -1, -1):
if grid[row][col] == 0:
new_place = max(new_place, row)
elif new_place >= 0:
grid[row][col], grid[new_place][col] = grid[new_place][col], grid[row][col]
new_place -= 1
# Crush and gravitate until no more moves
while not check_crush():
gravity()
return grid
The Candy Crush game implemented in Python involves a class named Game with a method processBoard that processes the board to simulate the game logic. The method accepts a 2D list grid, representing the game board where each cell contains an integer corresponding to different candy types or zero representing an empty space.
Process entails two main phases within
processBoard:- Identify and mark crushable candies.
- Apply gravity to drop candies into empty spaces.
The function
check_crushtraverses the board to find sequences of three or more candies of the same type either vertically or horizontally:- If such sequences are found, the method marks these candies by negating their values. This marking helps in identifying which candies to crush.
- After marking, the same function sets the marked candies' values to zero, simulating their removal from the board.
The function
gravitysimulates the gravity within the game:- It iterates through each column, moving non-zero values (candies) downwards into zero-valued positions (empty spaces), simulating the falling of candies due to gravity.
- Initially identifies the next available position for each candy as it scans from the bottom of the column upwards and swaps positions accordingly to simulate the drop.
The main loop within
processBoardcontinues to alternate between crushing and applying gravity until no more candies can be crushed, indicated bycheck_crushreturningTrue.
The game logic closely mirrors the actual play mechanics of Candy Crush, where matching rows or columns of candies are eliminated and candies above drop down to fill the spaces. This makes the board dynamic and continuously changing as moves are made. The final output of processBoard is the modified grid after all possible moves are completed.
No comments yet.