C++ 中击中砖块时掉落

c++server side programmingprogramming

假设我们有一个二进制值(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，则−
- return 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)
return ret
定义一个函数 notConnected()，它将接受 x、y 和 grid，
初始化 k := 0，当 k < 4 时，更新(将 k 增加 1)，执行 −
- nx := x + dir[k, 0], ny := y + dir[k, 1]
- 如果 (nx, ny) 在 grid 范围内，则 −
  - 忽略以下部分，跳到下一次迭代
- 如果 grid[nx, ny] 与 2 相同，则 −
  - return 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)，则 −
  - 在 ret 末尾插入 dfs(x, y, grid)
- 否则
  - 在 ret 末尾插入 0
反转数组 ret
return 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));
}