C++で解く「レンガが落ちる」問題：ヒット時に落下するレンガの数を求める

問題概要

0と1で構成されるグリッドを考えます。値が1のセルはレンガを表しています。レンガが落下せずに安定していられるのは、次のいずれかの条件を満たす場合です。

• そのレンガがグリッドの最上部に直接接している
• または、隣接する（上下左右の）レンガのうち、少なくとも1つが落下しない安定なレンガとつながっている

このグリッドに対して、指定された順番で消去操作を行います。各操作では位置 (i, j) が与えられ、そこにレンガが存在すればそれが消滅し、その結果として他のレンガが連鎖的に落下することがあります。各消去操作の後に落下したレンガの数を、操作順に並べた配列を求めるのがこの問題のゴールです。

たとえば、入力が grid = [[1,0,0,0],[1,1,1,0]]、hits = [[1,0]] の場合、出力は [2] になります。(1, 0) のレンガを取り除くと、支えを失った (1, 1) と (1, 2) のレンガが落下するためです。

解法の考え方：時間を逆順にたどる

ヒットを正順でシミュレートすると落下判定が複雑になりますが、「逆再生」の発想を使うとシンプルに解けます。まずすべてのヒットを先に適用しておき、その状態で最上部につながっている安定なレンガをDFSでマークします。その後、ヒットを逆順に復元しながら、復元したレンガが安定領域につながるかどうかを確認すればよいのです。

手順

• 4方向の移動量を表す配列 dir を用意します: {{1,0}, {-1,0}, {0,1}, {0,-1}}
• 関数 dfs(i, j, grid)
  • (i, j) がグリッドの範囲外、または grid[i][j] が1でない場合は 0 を返す
  • ret := 1 とし、grid[i][j] := 2 に更新する（安定マーク）
  • 4方向それぞれについて ret := ret + dfs(隣接セル) を実行する
  • ret を返す
• 関数 notConnected(x, y, grid)
  • 4方向の隣接セル (nx, ny) を調べ、範囲内かつ grid[nx][ny] == 2（安定なレンガ）であれば true を返す
  • x == 0（最上部の行）であれば true を返す
• メイン処理
  • 結果格納用の配列 ret を用意する
  • すべてのヒット位置について grid[hits[i][0]][hits[i][1]] を 1 減らす（レンガを事前に取り除いておく）
  • 最上行の各セルに対して dfs を実行し、安定している領域をすべて 2 でマークする
  • hits 配列を反転し、各ヒットを逆順に復元する
    • grid[x][y] += 1 でレンガを元に戻す
    • grid[x][y] == 1 かつ notConnected(x, y, grid) が成り立つなら、dfs(x, y, grid) - 1 を ret の末尾に追加する（-1 は復元したレンガ自身を「落下」と数えないため）
    • それ以外の場合は 0 を ret の末尾に追加する
  • 最後に ret を反転して返す

なお、この手法の計算量は最悪の場合 O(ヒット数 × マス数) となります。各ヒットの復元時にDFSで最大でもグリッド全体を一度走査するだけなので、十分に実用的な速度で動作します。

C++実装例

#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[0].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]