Easy to understand C# version


  • 0
    M
    1. find the ajacent items in both columns and rows, record their positions in a list, but do not change them yet
    2. after finding all, change them
    3. use slow/fast pointers to eliminate the 0s in the middle of each column
    4. recursively do the same thing again, if ever found the ajacent items last time
        private struct P
        {
            public int x;
            public int y;
            public P(int x, int y) { this.x = x; this.y = y; }
        }
        public int[,] CandyCrush(int[,] board)
        {
            int m = board.GetLength(0), n = board.GetLength(1);
            
            bool found = false;
            List<P> list = new List<P>();
            for (int i = 0; i < board.GetLength(0); i++)                              // found in rows
            {
                int j = 0, jj = j+1;
                while (j < board.GetLength(1) && jj < board.GetLength(1))
                {
                    while (jj < board.GetLength(1) && board[i, jj] == board[i, j] && board[i,j] != 0) jj++;
                    if (jj - j >= 3)
                    {
                        found = true;
                        for (int k = j; k < jj; k++) list.Add(new P(i, k));
                    }
                    j = jj;
                    jj = j+1;
                }
            }
            for (int j = 0; j < board.GetLength(1); j++)                             // found in columns
            {
                int i = 0, ii = i+1;
                while (i < board.GetLength(0) && ii < board.GetLength(0))
                {
                    while (ii < board.GetLength(0) && board[ii, j] == board[i, j] && board[i,j] != 0) ii++;
                    if (ii - i >= 3)
                    {
                        found = true;
                        for (int k = i; k < ii; k++) list.Add(new P(k, j));
                    }
                    i = ii;
                    ii = i+1;
                }
            }
            
            foreach (P p in list)board[p.x, p.y] = 0;                               // change the original matrix
            
            if (found) {
                for (int j = 0; j < board.GetLength(1); j++)                        // eliminate 0s in the middle of each line   
                {
                    int slow = board.GetLength(0) - 1;
                    while (slow >= 0 && board[slow, j] != 0) slow--;
                    int fast = slow-1;
                    while (fast >= 0 && slow >= 0)
                    {
                        while (fast >= 0 && board[fast, j] == 0) fast--;
                        if (fast >= 0) board[slow--, j] = board[fast--, j];
                    }
                    for (int k = 0; k <= slow; k++) board[k, j] = 0;
                }
                CandyCrush(board);                                                  // recursively call again
            }
            return board;
        }
    

Log in to reply
 

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