数据结构
网络
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 次浏览
