C++でヒットするとレンガが落ちる

• どちらのブリックもグリッドの上部に直接接続されています

• または、隣接する（上、下、左、右）レンガの少なくとも1つが落下しません。

いくつかの消去を順番に行います。いずれの場合も、その場所（i、j）で消去を実行すると、その場所のブリック（存在する場合）が消え、その消去のために他のブリックがドロップする可能性があります。順番に消去するたびにドロップするレンガの数を表す配列を見つける必要があります。

したがって、入力がgrid =[[1,0,0,0]、[1,1,1,0]]のようで、ヒット=[[1,0]]の場合、出力は[2]になります。これは、（1、0）に配置されたレンガを削除すると、（1、1）と（1、2）のレンガがドロップするためです。したがって、2を返す必要があります。

これを解決するには、次の手順に従います-

• サイズの配列dirを定義します：4 x 2、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 <ヒットのサイズの場合、更新（iを1増やします）、実行-

  • grid [hits [i、0]、hits [i、1]]：=grid [hits [i、0]、hits [i、1]]-1

• 初期化i：=0の場合、i <グリッドのサイズの場合、更新（iを1増やします）、実行-

  • dfs（0、i、grid）

• 配列ヒットを逆にする

• 初期化i：=0の場合、i <ヒットのサイズの場合、更新（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

• 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, ]