723. Candy Crush

https://leetcode.com/problems/candy-crush/leetcode.com

Candy Crush 玩儿多了，结果这题想当然地把 crush 条件理解成了三个相同 candy 触碰在一起，就按照Q695来找 area>=3 的 island 了，但怎么改都不对，最后看solution才明白原来是必须垂直或者水平连接的三个才可以crush，反而简单多了。

695. Max Area of Island

比较难写的是 crush 之后 drop 的过程，这边把每一垂直列当成array，用双指针two pointer处理了，问题可以看作不停地往前填补array中的0，最后填了多少个就再在尾部添加上多少个0.

没有任何可以crush的再返回，用recursive调用函数自己搞定。

1/4/2021 Update:

其实扫描crush的过程很像CNN，长三格或高三格的滑动窗口 slide through 整个 board，发现需要 crush 的就记录。

drop candy 的过程可以理解为双指针交换元素，A指针是非0元素就交换，同时移动B，保持一直移动A，直到B移出范围。

单函数

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        m, n = len(board), len(board[0])
        toCrush = set()
        for i in range(m):
            for j in range(n):
                if all([board[i][j], i>1, board[i][j] == board[i-1][j] == board[i-2][j]]):
                    toCrush.update({(i,j), (i-1,j), (i-2,j)})
                if all([board[i][j], j>1, board[i][j] == board[i][j-1] == board[i][j-2]]):
                    toCrush.update({(i,j), (i,j-1), (i,j-2)})

        if toCrush:
            for y, x in toCrush: board[y][x] = 0

            for j in range(n):
                vertical = m-1
                for i in range(m-1, -1, -1):
                    if board[i][j] > 0:
                        board[vertical][j] = board[i][j]
                        vertical -= 1      
                for i in range(vertical+1):
                    board[i][j] = 0

            board = self.candyCrush(board)

        return board

多函数

class Solution:
    def candyCrush(self, board: List[List[int]]) -> List[List[int]]:
        crush = self.findCandy(board)
        if not crush:
            return board
        else:
            self.crushCandy(board, crush)
            self.dropCandy(board)    
            return self.candyCrush(board)
    
    
    def findCandy(self, board):
        m, n = len(board), len(board[0])
        toCrush = set()
        for i in range(m):
            for j in range(n):
                if all([board[i][j], i>1, board[i][j] == board[i-1][j] == board[i-2][j]]):
                    toCrush.update({(i,j), (i-1,j), (i-2,j)})
                if all([board[i][j], j>1, board[i][j] == board[i][j-1] == board[i][j-2]]):
                    toCrush.update({(i,j), (i,j-1), (i,j-2)})
        return toCrush
    
    
    def crushCandy(self, board, toCrush):
        for y, x in toCrush: 
            board[y][x] = 0
    
    
    def dropCandy(self, board):
        m, n = len(board), len(board[0])
        for j in range(n):
            A, B = m-1, m-1
            while A >= 0:
                if board[A][j] != 0:
                    board[A][j], board[B][j] = board[B][j], board[A][j]
                    B -= 1
                A -= 1