BricksFallingWhenHit803

fluency03 · fluency03 · commit 7d112f38ae34 · 2018-09-30T13:05:48.000+02:00
diff --git a/src/BricksFallingWhenHit803.java b/src/BricksFallingWhenHit803.java
@@ -138,5 +138,85 @@ public int top() {
             return sz[find(sz.length - 1)] - 1;
         }
     }
+
+
+    /**
+     * https://leetcode.com/problems/bricks-falling-when-hit/discuss/121072/Java-Solution
+     */
+    public int[] hitBricks2(int[][] grid, int[][] hits) {
+        if (hits.length == 0 || hits[0].length == 0) return null;
+        removeHitBrick(grid, hits);
+        markRemainBricks(grid);
+        return searchFallingBrick(grid, hits);
+    }
+
+    private void markRemainBricks(int[][] grid) {
+        for (int i = 0; i < grid[0].length; i++) {
+            deepSearch(grid, 0, i);
+        }
+    }
+
+    private void removeHitBrick(int[][] grid, int[][] hits) {
+        for (int i = 0; i < hits.length; i++) {
+            grid[hits[i][0]][hits[i][1]] = grid[hits[i][0]][hits[i][1]] - 1;
+        }
+    }
+
+    private int[] searchFallingBrick(int[][] grid, int[][] hits) {
+        int[] result = new int[hits.length];
+        for (int i = hits.length - 1; i >= 0; i--) {
+            if (grid[hits[i][0]][hits[i][1]] == 0) {
+                grid[hits[i][0]][hits[i][1]] = 1;
+                if (isConnectToTop(grid, hits[i][0], hits[i][1])) {
+                    result[i] = deepSearch(grid, hits[i][0], hits[i][1]) - 1;
+                } else {
+                    result[i] = 0;
+                }
+            }
+        }
+        return result;
+    }
+
+    private boolean isConnectToTop(int[][] grid, int i, int j) {
+        if(i == 0) return true;
+
+        if (i - 1 >= 0 && grid[i - 1][j] == 2) {
+            return true;
+        }
+        if (i + 1 < grid.length && grid[i + 1][j] == 2) {
+            return true;
+        }
+        if (j - 1 >= 0 && grid[i][j - 1] == 2) {
+            return true;
+        }
+        if (j + 1 < grid[0].length && grid[i][j + 1] == 2) {
+            return true;
+        }
+        return false;
+    }
+
+    private int deepSearch(int[][] data, int row, int column) {
+        int arrayRow = data.length;
+        int arrayLine = data[0].length;
+        int effectBricks = 0;
+        if (row < 0 || row >= arrayRow) return effectBricks;
+        if (column < 0 || column >= arrayLine) return effectBricks;
+        if (data[row][column] == 1) {
+            data[row][column] = 2;
+            effectBricks = 1;
+            effectBricks += deepSearch(data, row + 1, column);
+            effectBricks += deepSearch(data, row - 1, column);
+            effectBricks += deepSearch(data, row, column + 1);
+            effectBricks += deepSearch(data, row, column - 1);
+        }
+        return effectBricks;
+    }
+
+
+
+
+
+
+
 }
 
