//
// Created by 罗炳国 on 2023/10/31.
//

#ifndef PFJ_CODE026_HITBRICKS_H
#define PFJ_CODE026_HITBRICKS_H

#include "commonHeader.h"

/**
 *
 * 有一个 m x n 的二元网格 grid ，其中 1 表示砖块，0 表示空白。砖块 稳定（不会掉落）的前提是：
 * 一块砖直接连接到网格的顶部，或者
 *  至少有一块相邻（4 个方向之一）砖块 稳定 不会掉落时
 *  给你一个数组 hits ，这是需要依次消除砖块的位置。每当消除 hits[i] = (rowi, coli) 位置上的砖块时，对应位置的砖块（若存在）会消失，然后其他的砖块可能因为这一消除操作而 掉落 。
 *  一旦砖块掉落，它会 立即 从网格 grid 中消失（即，它不会落在其他稳定的砖块上）。
 *  返回一个数组 result ，其中 result[i] 表示第 i 次消除操作对应掉落的砖块数目。
 *  注意，消除可能指向是没有砖块的空白位置，如果发生这种情况，则没有砖块掉落。
 * https://leetcode.cn/problems/bricks-falling-when-hit/
 * */

class code026_hitBricks {
public:
    vector<int> hitBricks(vector<vector<int>>& grid, vector<vector<int>>& hits) {
        N = grid.size();
        M = grid[0].size();

        int hlen = hits.size();

        vector<int> ans(hlen, 0);
        if (N == 1)
            return ans;
        // 1.将消除位置--
        for (auto &v : hits) {
            grid[v[0]][v[1]]--;
        }
        // 2.天花板感染
        for (int i = 0; i < M; i++) {
            dfs(grid, 0, i);
        }

        // 3.时光回溯
        for (int i = hlen - 1; i >= 0; i--) {
            auto &v = hits[i];
            int row = v[0], col = v[1];

            grid[row][col]++;
            if(worth(grid, row, col)) {
                ans[i] = dfs(grid, row, col) - 1;
            }
        }
        return ans;
    }

    // 从i, j出发，遇到1就感染成2，统计感染了几个2
    int dfs(vector<vector<int>> &grid, int i, int j) {
        if(i < 0 || i == N || j == M || j < 0 || grid[i][j] != 1)
            return 0;
        grid[i][j] = 2;
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }

    bool worth(vector<vector<int>> &grid, int i, int j) {
        return grid[i][j] == 1 &&
               (i == 0  || (i > 0 && grid[i - 1][j] == 2)
                        || (i < N - 1 && grid[i + 1][j] == 2)
                        || (j > 0 && grid[i][j - 1] == 2)
                        || (j < M - 1 && grid[i][j + 1] == 2));
    }

    int N, M;



    void test() {
        vector<vector<int>> grid = {{1,0,0,0}, {1,1,1,0}};
        vector<vector<int>> hits = {{1,0}};
        vector<int> ans = hitBricks(grid, hits);
        vecShow(ans);
    }
};

#endif//PFJ_CODE026_HITBRICKS_H