723.粉碎糖果

723.粉碎糖果

题目大意:就是消消乐,横竖数字相同且连起来大于3的消掉.

解题思路:暴力法,遍历每个位置,然后检查是否有横竖连续大于3的,有就将该位置记录在to_crash中.然后对 to_crash中的点进行处理,直到to_Crash为空.画图模拟比较好理解.

class Solution {
public:
    vector<vector<int>> candyCrush(vector<vector<int>>& board) {
        int m = board.size();
        int n = board[0].size();       
        while (true) {
            vector<pair<int, int>> to_crash;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j]) {  //为了减小计算量,元素为0的略过
                        int i1 = i, i0 = i, j1 = j, j0 = j;  //  i1,i0,j1,j0分别为向下,向上,向右,向左的检测
                        //对每个点(i,j),以其为中心,向上下或左右方向扩展,看是否有连续
                        while (i1 < m && i1 < i+3 && board[i1][j] == board[i][j]) i1++;
                        while (i0 >= 0 && i0 > i-3 && board[i0][j] == board[i][j]) i0--;
                        while (j1 < n && j1 < j+3 && board[i][j1] == board[i][j]) j1++;
                        while (j0 >= 0 && j0 > j-3 && board[i][j0] == board[i][j]) j0--;
                        if (i1-i0 > 3 || j1-j0 > 3) to_crash.push_back({i,j});  //上下或左右连续元素超过3,即符合
                    }
                }
            }
            if (to_crash.empty()) break;
            for (auto t : to_crash) board[t.first][t.second] = 0;  //重点:将所有标记位置置0
            for (int j = 0; j < n; j++) {  //由于是自上往下消除,因此外层对j(纵坐标)循环     
                int t = m-1;  //t用于记录新board的横坐标
                for (int i = m-1; i >= 0; i--) {  //从下往上,非0元素参与交换,每次交换后t上移
                    if (board[i][j]) swap(board[i][j], board[t--][j]);
                }
            }
        }
        return board;
    }
};