벽돌 을 치다

우 리 는 1 과 0 을 포함 하 는 격자 가 있다.벽돌벽돌 한 조각 이 격자 의 꼭대기 에 직접 연결 되 거나 최소한 한 조각 (4 개 방향 중 하나) 의 벽돌 이 떨 어 지지 않 을 때 만 떨 어 지지 않 는 다.우 리 는 순서대로 벽돌 을 제거 할 것 이다.우리 가 (i, j) 위 치 를 없 앨 때마다 해당 위치 에 있 는 벽돌 (존재 한다 면) 이 사라 지고 다른 벽돌 은 이것 때문에 떨 어 질 수 있다.떨 어 진 벽돌 수 를 제거 할 때마다 배열 을 되 돌려 줍 니 다.
예시 1: 입력: grid = [1, 0, 0, 0], [1, 1, 1, 0] hits = [1, 0] 출력: [2] 설명: 우리 가 (1, 0) 위치의 벽돌 을 없 애 면 (1, 1) 과 (1, 2) 의 벽돌 이 떨어진다.그래서 우 리 는 2 로 돌아 가 야 한다.
예 2: 입력: grid = [1, 0, 0, 0], [1, 1, 0, 0] hits = [1, 1], [1, 0] 수출: [0, 0] 은 우리 가 (1, 0) 벽돌 을 없 앨 때 (1, 1) 벽돌 은 이미 지난 단계 에 없어 져 사 라 졌 다 고 설명 했다.그래서 매번 작업 을 없 앨 때마다 벽돌 이 떨 어 지지 않 습 니 다.벽돌 이 떨 어 진 벽돌 로 기억 되 지 않도록 주의 하 세 요.주의:
격자 의 줄 수 와 열의 범 위 는 [1, 200] 이다.제 거 된 숫자 는 격자 영역 을 초과 하지 않 습 니 다.매번 제거 가 다 르 고 그리드 내부 에 있 음 을 보증 할 수 있 습 니 다.제 거 된 위치 에 벽돌 이 없 을 수도 있 고, 이렇게 되면 벽돌 이 떨 어 지지 않 을 수도 있다.
해답: 두 드 리 기 전에 근처 의 칸 이 꼭대기 에 있 는 지, 꼭대기 에 있 으 면 떨 어 지지 않 고 떨 어 질 때 숫자 를 집계 하 는 방향 으로 생각 하고 있다.오래 걸 려 서 좀 부끄럽다
코드:

int[][] his;
int xLen;
int yLen;

public int[] hitBricks(int[][] grid, int[][] hits) {
    int[] ans = new int[hits.length];
    xLen = grid.length;
    yLen = grid[0].length;
    his = new int[xLen][yLen];
    for (int i = 0; i < hits.length; i++) {
        int x = hits[i][0];
        int y = hits[i][1];
        if (grid[x][y] == 0) {
            ans[i] = 0;
            continue;
        }
        grid[x][y] = 0;
        ans[i] += hit(x, y - 1, grid, i + 1);
        ans[i] += hit(x, y + 1, grid, i + 1);
        ans[i] += hit(x - 1, y, grid, i + 1);
        ans[i] += hit(x + 1, y, grid, i + 1);
    }
    return ans;
}

private int hit(int x, int y, int[][] grid, int hisV) {
    if (x < 0 || x >= xLen || y < 0 || y >= yLen) {
        return 0;
    }
    if (grid[x][y] == 0) {
        return 0;
    }
    boolean kq = getKq(x, y, grid, hisV);
    if (kq) {
        return 0;
    }
    return remove(x, y, grid);
}

private int remove(int x, int y, int[][] grid) {
    if (x < 0 || x >= xLen || y < 0 || y >= yLen) {
        return 0;
    }
    if (grid[x][y] == 0) {
        return 0;
    }
    grid[x][y] = 0;
    int ans = 1;
    ans += remove(x - 1, y, grid);
    ans += remove(x + 1, y, grid);
    ans += remove(x, y - 1, grid);
    ans += remove(x, y + 1, grid);
    return ans;
}

private boolean getKq(int x, int y, int[][] grid, int hisV) {
    if (x == xLen || y == yLen || y < 0) {
        return false;
    }
    if (grid[x][y] == 0) {
        return false;
    }
    if (x == 0) {
        return true;
    }
    if (his[x][y] == hisV) {
        return true;
    }
    if (his[x][y] == 0 - hisV) {
        return false;
    }
    //      ，    
    his[x][y] = 0 - hisV;
    if (getKq(x - 1, y, grid, hisV)) {
        his[x][y] = hisV;
        return true;
    }
    if (getKq(x + 1, y, grid, hisV)) {
        his[x][y] = hisV;
        return true;
    }
    if (getKq(x, y - 1, grid, hisV)) {
        his[x][y] = hisV;
        return true;
    }
    if (getKq(x, y + 1, grid, hisV)) {
        his[x][y] = hisV;
        return true;
    }
    return false;
}

거꾸로 생각: 지금 은 다 친 상태 입 니 다. 얼마나 많은 칸 이 남아 있 는 지 보고 표 시 를 합 니 다.반대로 두 드 린 칸 을 붙 이면 얼마나 붙 일 수 있 습 니까?코드:

public int[] hitBricks(int[][] grid, int[][] hits) {
    int[] ans = new int[hits.length];
    //           
    for (int i = 0; i < hits.length; i++) {
        if (grid[hits[i][0]][hits[i][1]] == 1) {
            grid[hits[i][0]][hits[i][1]] = -1;
        }
    }
    for (int i = 0; i < grid[0].length; i++) {
        if (grid[0][i] == 1) {
            cleanToTwo(grid, 0, i);
        }
    }
    for (int i = hits.length - 1; i >= 0; i--) {
        //   
        if (grid[hits[i][0]][hits[i][1]] == -1 && nearTwo(grid, hits[i][0], hits[i][1])) {
            ans[i] = cleanToTwo(grid, hits[i][0], hits[i][1]) - 1;
        }
    }
    return ans;
}

//       2，     ，      1
private boolean nearTwo(int[][] grid, int x, int y) {
    grid[x][y] = 1;
    if (x == 0) {
        return true;
    }
    if (x > 0 && grid[x - 1][y] == 2) {
        return true;
    }
    if (x < grid.length - 1 && grid[x + 1][y] == 2) {
        return true;
    }
    if (y > 0 && grid[x][y - 1] == 2) {
        return true;
    }
    if (y < grid[0].length - 1 && grid[x][y + 1] == 2) {
        return true;
    }
    return false;
}

//       2
private int cleanToTwo(int[][] grid, int x, int y) {
    int ans = 1;
    grid[x][y] = 2;
    if (x > 0 && grid[x - 1][y] == 1) {
        ans += cleanToTwo(grid, x - 1, y);
    }
    if (x < grid.length - 1 && grid[x + 1][y] == 1) {
        ans += cleanToTwo(grid, x + 1, y);
    }
    if (y > 0 && grid[x][y - 1] == 1) {
        ans += cleanToTwo(grid, x, y - 1);
    }
    if (y < grid[0].length - 1 && grid[x][y + 1] == 1) {
        ans += cleanToTwo(grid, x, y + 1);
    }
    return ans;
}

}