Giả sử chúng ta có một lưới các giá trị nhị phân (0 và 1), các giá trị 1 trong một ô đại diện cho các khối hình. Một viên gạch sẽ không rơi khi thỏa mãn các điều kiện này -
-
Một trong hai viên gạch được kết nối trực tiếp với đầu của lưới
-
hoặc ít nhất một trong các viên gạch liền kề (trên, dưới, trái, phải) của nó sẽ không bị rơi xuống.
Chúng tôi sẽ thực hiện một số tẩy xóa theo tuần tự. Trong mỗi trường hợp chúng ta muốn xóa tại vị trí (i, j), viên gạch (nếu có) trên vị trí đó sẽ biến mất, và sau đó một số viên gạch khác có thể bị rơi ra do thao tác xóa đó. Chúng ta phải tìm mảng đại diện cho số lượng gạch sẽ giảm xuống sau mỗi lần xóa theo trình tự.
Vì vậy, nếu đầu vào giống như grid =[[1,0,0,0], [1,1,1,0]] và hits =[[1,0]], thì đầu ra sẽ là [2], điều này là do nếu chúng ta loại bỏ viên gạch đặt tại (1, 0), viên gạch tại (1, 1) và (1, 2) sẽ giảm xuống. Vì vậy, chúng ta nên quay trở lại 2.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
Xác định dir mảng có kích thước:4 x 2, dir:={{1, 0}, {- 1, 0}, {0, 1}, {0, - 1}}
-
Xác định một hàm dfs (), điều này sẽ lấy i, j, lưới,
-
nếu khi (i, j) nằm trong vùng lưới và lưới [i, j] không bằng 1, thì−
-
trả về 0
-
-
ret:=1
-
lưới [i, j]:=2
-
để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -
-
ret:=ret + dfs (i + dir [k, 0], j + dir [k, 1], grid)
-
-
trả lại ret
-
Xác định một hàm notConnected (), hàm này sẽ lấy x, y và lưới,
-
để khởi tạo k:=0, khi k <4, cập nhật (tăng k lên 1), thực hiện -
-
nx:=x + dir [k, 0], ny:=y + dir [k, 1]
-
nếu (nx, ny) nằm trong phạm vi lưới, thì -
-
Bỏ qua phần sau, chuyển sang phần tiếp theo
-
-
nếu lưới [nx, ny] giống 2 thì -
-
trả về true
-
-
-
trả về true khi x giống 0
-
Từ phương thức chính, thực hiện như sau -
-
Xác định ret mảng
-
để khởi tạo i:=0, khi tôi
-
grid [hits [i, 0], hits [i, 1]]:=grid [hits [i, 0], hits [i, 1]] - 1
-
-
để khởi tạo i:=0, khi i
-
dfs (0, i, lưới)
-
-
đảo ngược các lần truy cập mảng
-
để khởi tạo i:=0, khi tôi
-
x:=hits [i, 0], y:=hits [i, 1]
-
nếu grid [x, y] giống 1 và notConnected (x, y, grid), thì -
-
chèn dfs (x, y, lưới) vào cuối ret
-
-
Nếu không
-
chèn 0 vào cuối ret
-
-
-
đảo ngược mảng ret
-
trả lại ret
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
#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));
} Đầu vào
{{1,0,0,0},{1,1,1,0}}, {{1,0}} Đầu ra
[2, ]