資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++中磚塊被擊中時掉落
假設我們有一個二進位制值（0和1）的網格，單元格中的1表示磚塊。當滿足以下條件時，磚塊不會掉落：
磚塊直接連線到網格頂部
或者其至少一個相鄰（上、下、左、右）磚塊不會掉落。
我們將依次進行一些擦除操作。在每種情況下，我們都希望在位置（i，j）進行擦除，該位置上的磚塊（如果存在）將消失，然後其他一些磚塊可能會由於該擦除而掉落。我們必須找到表示每次擦除後掉落磚塊數量的陣列。
因此，如果輸入類似於 grid = [[1,0,0,0],[1,1,1,0]] 和 hits = [[1,0]]，則輸出將為 [2]，這是因為如果我們移除位於 (1, 0) 的磚塊，則位於 (1, 1) 和 (1, 2) 的磚塊將掉落。因此，我們應該返回 2。
為了解決這個問題，我們將遵循以下步驟：
定義一個大小為 4 x 2 的陣列 dir，dir := {{1, 0}, { - 1, 0}, {0, 1}, {0, - 1}}
定義一個函式 dfs()，它將接收 i、j 和網格作為引數。
如果 (i,j) 在網格區域內並且 grid[i, j] 不等於 1，則：
返回 0
ret := 1
grid[i, j] := 2
從 k := 0 開始，當 k < 4 時，更新（將 k 增加 1），執行：
ret := ret + dfs(i + dir[k, 0], j + dir[k, 1], grid)
返回 ret
定義一個函式 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
從 i := 0 開始，當 i < hits 的大小時，更新（將 i 增加 1），執行：
grid[hits[i, 0], hits[i, 1]] := grid[hits[i, 0], hits[i, 1]] - 1
從 i := 0 開始，當 i < grid 的大小時，更新（將 i 增加 1），執行：
dfs(0, i, grid)
反轉陣列 hits
從 i := 0 開始，當 i < hits 的大小時，更新（將 i 增加 1），執行：
x := hits[i, 0], y := hits[i, 1]
如果 grid[x, y] 與 1 相同且 notConnected(x, y, grid) 為 true，則：
在 ret 的末尾插入 dfs(x, y, grid)
否則
在 ret 的末尾插入 0
反轉陣列 ret
返回 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, ]
120 次瀏覽
