C++で爆弾1つで倒せる最大の敵の数を求めるプログラム

問題の概要

2次元のグリッド（行列）が与えられ、その各セルには「2」「1」「0」の3種類の値が入っています。「2」は敵、「1」は壁、「0」は空きマスを表します。この中で、爆弾を1つだけ設置して倒せる最大の敵の数を求めるのがこの問題です。

爆弾の仕様は以下の通りです。

• 爆弾は設置された地点から、同じ行と同じ列にある敵をすべて倒します。
• 爆弾の効果は壁にぶつかった時点で止まります。
• 爆弾を設置できるのは空きマス（0）のみです。

例えば、以下のようなグリッドが入力として与えられた場合を考えてみましょう。

この場合の出力は 3 になります。緑色のマスに爆弾を設置することで、最大3体の敵を倒せるからです。

アルゴリズム

この問題を効率的に解くには、各行・各列ごとに「壁で区切られた区間内の敵の数」を事前に計算しておくのがポイントです。手順は以下の通りです。

1. 結果を格納する変数 ret := 0 を初期化します。
2. グリッドの行数を n、列数を m とします。
3. サイズ m の配列 colCnt を用意し、各列の敵のカウントを管理します。
4. グリッド全体を走査しながら、以下の処理を行います。
   • 行方向の処理： 行の先頭（j = 0）または現在のセルが壁の場合、rowCnt をリセットし、次の壁に到達するまでの敵の数を数えます。
   • 列方向の処理： 列の先頭（i = 0）または現在のセルが壁の場合、colCnt[j] をリセットし、次の壁に到達するまでの敵の数を数えます。
   • 現在のセルが空きマス（0）の場合、ret を rowCnt + colCnt[j] の最大値で更新します。
5. 最後に ret を返します。

この方法により、各セルを一度ずつ走査するだけで答えが求まり、計算量は O(n×m) に抑えられます。

C++での実装例

理解を深めるために、以下の実装をご覧ください。

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
   int solve(vector<vector<int>>& grid) {
      int ret = 0;
      int n = grid.size();
      int m = n ? grid[0].size() : 0;
      int rowCnt = 0;
      vector<int> colCnt(m);
      for (int i = 0; i < n; i++) {
         for (int j = 0; j < m; j++) {
            if (!j || grid[i][j] == 1) {
               rowCnt = 0;
               int k;
               if (grid[i][j] == 1)
                  k = j + 1;
               else
                  k = j;
               for (; k < m && grid[i][k] != 1; k++) {
                  rowCnt += (grid[i][k] == 2);
               }
            }
            if (!i || grid[i][j] == 1) {
               colCnt[j] = 0;
               int k;
               if (grid[i][j] == 1)
                  k = i + 1;
               else
                  k = i;
               for (; k < n && grid[k][j] != 1; k++) {
                  colCnt[j] += (grid[k][j] == 2);
               }
            }
            if (grid[i][j] == 0) {
               ret = max(ret, rowCnt + colCnt[j]);
            }
         }
      }
      return ret;
   }
};

main(){
   Solution ob;
   vector<vector<int>> v = {
      {0,2,0,0},
      {2,0,1,2},
      {0,2,0,0}};
   cout << (ob.solve(v));
}

入力

{{0,2,0,0},
{2,0,1,2},
{0,2,0,0}}

出力

3

まとめ

この問題は、単純に全マスについて毎回行・列の敵を数え直すと O(n²m²) の計算量になってしまいますが、壁で区切られた区間ごとにカウントを再利用する工夫により、O(n×m) まで高速化できます。動的プログラミング的な「前回の計算結果を活かす」発想は、グリッド系の問題で頻出するテクニックなので、ぜひ覚えておきましょう。