Mid/Senior
Candy Crush
Given an m x n integer matrix board representing a Candy Crush board, where each positive integer represents a type of candy and 0 represents an empty cell, repeatedly perform the following operations until the board is stable:
- Find every group of three or more candies of the same type that are adjacent horizontally or vertically in a contiguous line.
- Crush all such candies simultaneously, making their cells empty.
- Let candies above empty cells fall down vertically to fill those spaces, leaving
0s at the top of each column.
Return the final stable board after no more candies can be crushed.
Example 1
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
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]]After repeatedly crushing all horizontal and vertical groups of at least three candies and applying gravity, the board reaches the shown stable state.
Example 2
1 2 3 4 5 6 7 8 9
Input
board = [[1,2,3],[4,5,6],[7,8,9]]Output
[[1,2,3],[4,5,6],[7,8,9]]There are no three matching candies in a contiguous horizontal or vertical line, so the board is already stable.
Constraints
- 3 <= board.length <= 50
- 3 <= board[i].length <= 50
- 1 <= board[i][j] <= 2000