05 August 2008
2D数组上消除
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.
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.length n == board[i].length 3 <= m, n <= 50 1 <= board[i][j] <= 2000
这道题一次消除 table 中所有可消除的糖果，然后才下落，形成新的 table，这样消除后得到的结果就是统一的了，这样也大大的降低了难度。下面就来看如何找到要消除的糖果，可能有人会觉得像之前的岛屿的题目一样找连通区域，可是这道题的有限制条件，只有横向或竖向相同的糖果数达到三个才能消除，并不是所有的连通区域都能消除，所以找连通区域不是一个好办法。
最好的办法其实是每个糖果单独检查其是否能被消除，然后把所有能被删除的糖果都标记出来统一删除，然后在下落糖果，然后再次查找，直到无法找出能够消除的糖果时达到稳定状态。好，用一个数组来保存可以被消除的糖果的位置坐标，判断某个位置上的糖果能否被消除的方法就是检查其横向和纵向的最大相同糖果的个数，只要有一个方向达到三个了，当前糖果就可以被消除。所以对当前糖果的上下左右四个方向进行查看，用四个变量 x0, x1, y0, y1，其中 x0 表示上方相同的糖果的最大位置，x1 表示下方相同糖果的最大位置，y0 表示左边相同糖果的最大位置，y1 表示右边相同糖果的最大位置，均初始化为当前糖果的位置，然后使用 while 循环向每个方向遍历，注意并不需要遍历到尽头，而是只要遍历三个糖果就行了，因为一旦查到了三个相同的，就说明当前的糖果已经可以消除了，没必要再往下查了。查的过程还要注意处理越界情况，好，得到了上下左右的最大的位置，分别让相同方向的做差，如果水平和竖直方向任意一个大于3了，就说明可以消除，将坐标加入数组 del 中。注意这里一定要大于3，是因为当发现不相等退出 while 循环时，坐标值已经改变了，所以已经多加了或者减了一个，所以差值要大于3。遍历完成后，如果数组 del 为空，说明已经 stable 了，直接 break 掉，否则将要消除的糖果位置都标记为0，然后进行下落处理。下落处理实际上是把数组中的0都移动到开头，那么就从数组的末尾开始遍历，用一个变量t先指向末尾，然后然后当遇到非0的数，就将其和t位置上的数置换，然后t自减1，这样t一路减下来都是非0的数，而0都被置换到数组开头了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public int[][] candyCrush(int[][] board) {
int rows = board.length;
int cols = rows == 0 ? 0 : board[0].length;
boolean todo = false;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols - 2; col++) {
int val = Math.abs (board[row][col]);
if (val != 0 && val == Math.abs (board[row][col + 1]) && val == Math.abs (board[row][col + 2])) {
todo = true;
board[row][col] = board[row][col + 1] = board[row][col + 2] = -val;
}
}
}
for (int col = 0; col < cols; col++) {
for (int row = 0; row < rows - 2; row++) {
int val = Math.abs (board[row][col]);
if (val != 0 && val == Math.abs (board[row + 1][col]) && val == Math.abs (board[row + 2][col])) {
todo = true;
board[row][col] = board[row + 1][col] = board[row + 2][col] = -val;
}
}
}
for (int col = 0; col < cols; col++) {
int row2 = rows - 1;
for (int row1 = rows - 1; row1 >= 0; row1--) {
if (board[row1][col] > 0) {
board[row2--][col] = board[row1][col];
}
}
while (row2 >= 0) {
board[row2--][col] = 0;
}
}
return todo ? candyCrush (board) : board;
}
}