candy crush
723. Candy Crush
- 方法1:
- 易错点：
- Complexity
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:
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 (ie. 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.
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:
Note:
- 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].
方法1:
思路：
首先应该确定整体的步骤是一个recursion，可以在遍历的过程中记录一个bool表示是否有需要消掉的candy，只要有，就需要在最后recursion，否则可以直接返回当前board。而在每一次递归中，分成两个阶段：1. 遍历第一次找到所有可以crash的地方，但是不能急于消掉，因为比如上面第一张图中的2，消掉纵行之后会导致剩下的横行消不掉。所以要找一个办法即记住它需要被消掉，但是还可以继续和不同方向的数字再比较，那么就想到了用符号来标记。下一步需要确定什么时候被crash：对每一个点，我们检查纵向或者横向是否有至少3个点能连起来（此时以左端点或顶点为轴心），如果可以就说明需要消掉，再次从轴心出发用双指针寻找连续的范围，一边走一边flip，并且mark changed。2. clear and gravity，第二次遍历从最下方开始，也是双指针的思想，high指针向上遍历找到上面的非负值时，就向low指针的位置drop。注意当high遍历结束后，low仍然需要遍历到底并将所有上方的格子清零。
易错点：
- 在判断连续时要排除0，很多0 都连在一起，而且只会越连越多，如果不排除recursion永远停不下来。
- gravity step 慢指针也要遍历到底：任务是清零。
Complexity
Time complexity: O(mn)
Space complexity: O(1)
class Solution {
public:
vector<vector<int>> candyCrush(vector<vector<int>>& board) {
if (board.size() < 3 && board[0].size() < 3) return board;
int m = board.size(), n = board[0].size();
bool changed = false;
// mark
for (int i = 0; i < m - 2; i++) {
for (int j = 0; j < n; j++) {
int val = abs(board[i][j]);
// vertical
if (val && val == abs(board[i + 1][j]) && val == abs(board[i + 2][j])) {
int high = i;
while (high < m && val == abs(board[high][j])) {
board[high++][j] = -val;
changed = true;
}
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 2; j++) {
int val = abs(board[i][j]);
// horizontal
if (val && val == abs(board[i][j + 1]) && val == abs(board[i][j + 2])) {
int right = j;
while (right < n && val == abs(board[i][right])) {
board[i][right++] = -val;
changed = true;
}
}
}
}
// gravity
for (int j = 0; j < n; j++) {
int bottom = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] > 0) board[bottom--][j] = board[i][j];
}
while (bottom >= 0) board[bottom--][j] = 0;
}
return changed ? candyCrush(board) : board;
}
};
相关阅读
（文/ Douglas Heaven）2014年4月，一则美国游戏业界已经流传了几十年的传闻，在新墨西哥州的一处垃圾掩埋场得到了证实。故事要回溯到198