723. Candy Crush

這題其實除了題目有趣(就是candy crush), 其實沒有用到什麼高深的演算法

但難在其實也不好著手

大概說明一下, 會先用for迴圈掃完整個矩陣, 然後判定每個點, 是否要被清空, 清空的條件就是上下左右是否三連, 一旦需要清空就加到vector

最後清完後, 把每個col 的值都從下往上擺好

然後重複上述循環 直到找不到要清空的點

說來容易, 要做一開始我還真的不知道怎麼下筆

class Solution {
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& b) {
        int m = b.size();
        int n = b[0].size();
        while(true){
            vector<pair<int, int>> vp;
            for(int i =0;i< m;i++){
                for(int j =0; j <n;j++){
                    if(b[i][j] > 0){ // has candy
                        int i0 = i;
                        int i1 = i;
                        int j0 = j;
                        int j1 = j;
                        while(i1 < m && i1 < i + 3 && b[i1][j]==b[i][j])
                            i1++;
                        while(i0 >=0 && i0>i - 3 && b[i0][j]==b[i][j])
                            i0--;
                        while(j1 < n && j1 < j + 3 && b[i][j1] == b[i][j])
                            j1++;
                        while(j0 >= 0 && j0 > j -3 && b[i][j0] == b[i][j])
                            j0--;
                        if(i1 - i0 > 3 || j1- j0 > 3)
                            vp.push_back({i, j});
                    }
                }
            }
            if(vp.empty()) break;
            // crush
            for(auto p : vp){
                b[p.first][p.second] = 0;
            }
            // drop
            for(int j = 0; j < n;j++){
                int t = m - 1;
                // from bottom follow up
                for(int i = m - 1; i >= 0;i--){
                    if(b[i][j]){
                        swap(b[i][j], b[t][j]);
                        t--;
                    }
                }
                // clean t up
                for(int i = t; i >=0;i--){
                    b[i][j] = 0;
                }
            }
        }
        return b;
    }
};