Candy Crush, using negative numbers to label curshed candies


  • 0

    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);
            }
        }
    

Log in to reply
 

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