셀의 1이 벽돌을 나타내는 이진 값(0과 1)의 그리드가 있다고 가정합니다. 이 조건을 만족하면 벽돌이 떨어지지 않습니다 -
-
두 벽돌 중 하나가 그리드 상단에 직접 연결됩니다.
-
또는 인접한(위, 아래, 왼쪽, 오른쪽) 벽돌 중 하나 이상이 떨어지지 않습니다.
순차적으로 일부 삭제 작업을 수행합니다. 각각의 경우에 우리는 위치(i, j)에서 지우기를 원하고, 그 위치의 벽돌(있는 경우)이 사라지고 그 지우기로 인해 일부 다른 벽돌이 떨어질 수 있습니다. 우리는 순서대로 각 소거 후에 드롭될 벽돌의 수를 나타내는 배열을 찾아야 합니다.
따라서 입력이 grid =[[1,0,0,0],[1,1,1,0]]이고 hit =[[1,0]]인 경우 출력은 [2]가 됩니다. (1, 0)에 있는 벽돌을 제거하면 (1, 1), (1, 2)에 있는 벽돌이 떨어지기 때문입니다. 따라서 2를 반환해야 합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
배열 dir 크기 정의:4 x 2, dir :={{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}
-
dfs() 함수를 정의하면 i, j, 그리드,
-
(i,j)가 그리드 영역 안에 있고 grid[i, j]가 1이 아닌 경우 -
-
0 반환
-
-
렛 :=1
-
그리드[i, j] :=2
-
초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −
-
ret :=ret + dfs(i + dir[k, 0], j + dir[k, 1], 그리드)
-
-
리턴 렛
-
notConnected() 함수를 정의하면 x, y 및 그리드가 필요합니다.
-
초기화 k :=0의 경우 k <4일 때 업데이트(k를 1만큼 증가), −
-
nx :=x + dir[k, 0], ny :=y + dir[k, 1]
-
(nx, ny)가 그리드 범위에 있으면 -
-
다음 부분은 무시하고 다음 반복으로 건너뜁니다.
-
-
grid[nx, ny]가 2와 같으면 -
-
true를 반환
-
-
-
x가 0과 같을 때 true를 반환
-
기본 방법에서 다음을 수행하십시오 -
-
ret 배열 정의
-
for initialize i :=0, i <적중 크기, 업데이트(i 1 증가), −
-
grid[적중[i, 0], 적중[i, 1]] :=grid[적중[i, 0], 적중[i, 1]] - 1
-
-
initialize i :=0의 경우, i <그리드 크기일 때 업데이트(i를 1만큼 증가), 수행 -
-
dfs(0, i, 그리드)
-
-
배열 히트 반전
-
for initialize i :=0, i <적중 크기, 업데이트(i 1 증가), −
-
x :=조회수[i, 0], y :=조회수[i, 1]
-
grid[x, y]가 1이고 notConnected(x, y, grid)인 경우 -
-
ret의 끝에 dfs(x, y, grid) 삽입
-
-
그렇지 않으면
-
ret 끝에 0 삽입
-
-
-
ret 배열 반전
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
class Solution {
public:
int dfs(int i, int j, vector<vector<int> >& grid){
if (i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) {
return 0;
}
int ret = 1;
grid[i][j] = 2;
for (int k = 0; k < 4; k++) {
ret += dfs(i + dir[k][0], j + dir[k][1], grid);
}
return ret;
}
bool notConnected(int x, int y, vector<vector<int> >& grid){
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= grid.size() || ny >= grid[0].size())
continue;
if (grid[nx][ny] == 2) {
return true;
}
}
return x == 0;
}
vector<int> hitBricks(vector<vector<int> >& grid, vector<vector<int> >& hits){
vector<int> ret;
for (int i = 0; i < hits.size(); i++) {
grid[hits[i][0]][hits[i][1]] -= 1;
}
for (int i = 0; i < grid.size(); i++) {
dfs(0, i, grid);
}
reverse(hits.begin(), hits.end());
for (int i = 0; i < hits.size(); i++) {
int x = hits[i][0];
int y = hits[i][1];
grid[x][y] += 1;
if (grid[x][y] == 1 && notConnected(x, y, grid))
ret.push_back(dfs(x, y, grid) - 1);
else
ret.push_back(0);
}
reverse(ret.begin(), ret.end());
return ret;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{1,0,0,0},{1,1,1,0}};
vector<vector<int>> v1 ={{1,0}};
print_vector(ob.hitBricks(v, v1));
} 입력
{{1,0,0,0},{1,1,1,0}}, {{1,0}} 출력
[2, ]