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