# Candy Crush, using negative numbers to label curshed candies

• The trick in candy crush is to find a way to check if a particular slot will be crushed. (BFS and DFS is way more complicated in this problem)
We can find finite ways to form a match ( in this problem, the finite number is 6).

Think one more step further, how should we generate a `hint` for candy crush. A hint means possible ways of movement for the user when he/she is stuck at some point. In that case, the possible way is 16. (find more detailed explanation using google if you are interested).

``````    public int[][] candyCrush(int[][] board) {
if (board == null || board.length == 0 || board[0].length == 0) return board;
int cnt = 0;
int m = board.length, n = board[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 0) continue;
if (   (i > 0 && Math.abs(board[i-1][j]) == board[i][j] && (i < m - 1 && board[i+1][j] == board[i][j]))
|| (i > 1 && Math.abs(board[i-1][j]) == board[i][j] && Math.abs(board[i-2][j]) == board[i][j])
|| (i < m - 2 && board[i+1][j] == board[i][j] && board[i+2][j] == board[i][j])
|| (j > 0 && Math.abs(board[i][j-1]) == board[i][j] && (j < n - 1 && board[i][j+1] == board[i][j]))
|| (j > 1 && Math.abs(board[i][j-1]) == board[i][j] && Math.abs(board[i][j-2]) == board[i][j])
|| (j < n - 2 && board[i][j+1] == board[i][j] && board[i][j+2] == board[i][j])) {
cnt++;
board[i][j] = -board[i][j];
}
}
}
for (int j = 0; j < n; j++) {
int ptr = m - 1;
for (int i = m - 1; i >= 0; i--) {
if (board[i][j] > 0) {
board[ptr--][j] = board[i][j];
}
}
for (int i = ptr; i >= 0; i--) {
board[i][j] = 0;
}
}
if (cnt == 0) {
return board;
} else {
return candyCrush(board);
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.