package question;


public class Question803 {
 public static void main(String[] args) {
 //[[1,0,0,0],[1,1,1,0]], hits = [[1,0]]

 //[[1],[1],[1],[1],[1]]
 //[[3,0],[4,0],[1,0],[2,0],[0,0]]
 int[][] ints = {
 {1, 0, 0, 0}, {1, 1, 1, 0}
 };
 int[][] hits = {
 {1, 0}
 };
 for (int i : new Question803().hitBricks(ints, hits)) {
 System.out.print(i + " ");
 }
 }

 private static int[][] grid;
 private static int n, m;
 private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

 public int[] hitBricks(int[][] grid, int[][] hits) {
 this.grid = grid;
 n = grid.length;
 m = grid[0].length;
 int[] res = new int[hits.length];
 for (int[] hit : hits) {
 grid[hit[0]][hit[1]]--;
 }
 for (int i = 0; i < m; i++) {
 dfs(0, i);
 }
 for (int i = hits.length - 1; i >= 0; i--) {
 int x = hits[i][0];
 int y = hits[i][1];
 grid[x][y]++;
 if (grid[x][y] == 1 && isConnected(x, y))
 res[i] = dfs(x, y) - 1;
 }
 return res;
 }

 private int dfs(int x, int y) {
 if (!check(x, y)) return 0;
 if (grid[x][y] != 1) return 0;
 grid[x][y] = 2;
 int cnt = 1;
 for (int[] dir : DIRS) {
 int fx = x + dir[0];
 int fy = y + dir[1];
 cnt += dfs(fx, fy);
 }
 return cnt;
 }

 private boolean isConnected(int x, int y) {
 if (x == 0) return true;
 for (int[] dir : DIRS) {
 int fx = x + dir[0];
 int fy = y + dir[1];
 if (check(fx, fy) && grid[fx][fy] == 2) {
 return true;
 }
 }
 return false;
 }

 private boolean check(int x, int y) {
 return x >= 0 && x < n && y >= 0 && y < m;
 }
}