803. Bricks Falling When Hit

• 803. Bricks Falling When Hit
  • Description
  • Intuition
    • 正向DFS
    • 逆向DFS
  • Pitfall
  • Solution

Description

Here

Intuition

正向DFS

感觉上可以用正向DFS直接暴力，

  private static final int EMPTY = 0, BRICK = 1, VISITED = 2;
  private static final int[][] DIRS = {
      {0, 1}, {0, -1}, {1, 0}, {-1, 0}
  };

  public int[] hitBricks(int[][] grid, int[][] hits) {
    final int[] res = new int[hits.length];
    final int rows = grid.length, cols = grid[0].length;
    for (int i = 0; i < hits.length; i++) {
      final int[] hit = hits[i];
      System.out.println(Arrays.toString(hit));
      display(grid);
      grid[hit[0]][hit[1]] = 0;
      final int cur = dfs(grid, rows, cols, hit[0], hit[1]);
      if (cur != -1) {
        res[i] = cur;
      }
      display(grid);
    }
    return res;
  }

  /**
   * return -1 when found undroppable; otherwise, return the actual count;
   */
  private static int dfs(final int[][] grid, final int rows, final int cols, int row, int col) {
    grid[row][col] = 0;
    int res = 0;
    for (final int[] d : DIRS) {
      System.out.println(Arrays.toString(d));
      final int cur = dfsHelper(grid, rows, cols, row + d[0], col + d[1]);
      if (cur != -1) {
        res += cur;
      }
      display(grid);
    }
    return res;
  }

  private static int dfsHelper(final int[][] grid, final int rows, final int cols, int row, int col) {
    if (col < 0 || col >= cols || row >= rows || row < 0 || grid[row][col] == 0) {
      return 0;
    }
    if (row == 0) {
      return grid[row][col] == BRICK ? -1 : 0;
    }
    final int original = grid[row][col];
    grid[row][col] = 0;
    final int[] adjRes = {
        dfsHelper(grid, rows, cols, row + 1, col),
        dfsHelper(grid, rows, cols, row - 1, col),
        dfsHelper(grid, rows, cols, row, col + 1),
        dfsHelper(grid, rows, cols, row, col - 1)
    };
    if (adjRes[0] == -1 || adjRes[1] == -1 || adjRes[2] == -1 || adjRes[3] == -1) {
      grid[row][col] = original;
      return -1;
    }

    return 1 + adjRes[0] + adjRes[1] + adjRes[2] + adjRes[3];
  }

但这里有个问题

当 当前hit = [1, 3] 且

board =
[
    [0, 1, 1, 1, 1, 1]
    [1, 1, 1, 1, 1, 1]
    [0, 0, 1, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
    [0, 0, 0, 0, 0, 0]
]

且 direction = [0, -1]

则， 处理board[1][2]会出现以下问题：board[1][2]其实由于board[0][2]的问题无法消除，用以上rollback的方法无法将board[0][3] rollback成1

逆向DFS

可以先remove所有的hits，然后remove所有要掉的点，然后一点点加回来

Pitfall

Solution

-Reverse Dfs Solution