C++で解く爆弾敵問題（Bomb Enemy）― 1発の爆弾で倒せる敵の最大数を求めるアルゴリズム

問題の概要

2次元グリッドが与えられ、各セルは壁「W」、敵「E」、空きマス「0」のいずれかです。この問題では、1つの爆弾で倒せる敵の最大数を求めます。爆弾は設置した地点を起点として、同じ行・同じ列にいるすべての敵を、壁にぶつかるまで倒します。ただし、爆弾を設置できるのは空きマス（0）のみです。

例えば、次のようなグリッドが入力として与えられたとします。

この場合、出力は 3 となります。緑色のマスに爆弾を設置すると、3体の敵を同時に倒せるためです。

解法のアプローチ

すべてのマスについて毎回行・列の敵を数え直すと非効率です。そこで、行方向と列方向の敵の数を再利用することで計算を効率化します。具体的には、以下の手順で解きます。

• 答えを格納する変数 ret を 0 で初期化します。
• n をグリッドの行数、m を列数とします。
• 各列の敵の数を保持するため、サイズ m の配列 colCnt を用意します。
• グリッドを左上から順に走査します。各行について、行の先頭または壁に差しかかったタイミングで、次の壁（または行の終端）までの敵の数を rowCnt として数え直します。
• 同様に、列の先頭または壁に差しかかったタイミングで、次の壁（または列の終端）までの敵の数を colCnt[j] として数え直します。
• 現在のマスが空きマス「0」であれば、rowCnt + colCnt[j] がそのマスに爆弾を置いた場合の撃破数になります。この最大値を ret に記録していきます。
• 最後に ret を返します。

壁を境に区切られた区間ごとに敵の数を一度だけ数えるため、全体の計算量は O(n × m)、追加で必要なメモリは O(m) に抑えられます。

C++での実装例

理解を深めるために、以下の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int maxKilledEnemies(vector<vector<char>>& 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] == 'W') {
               rowCnt = 0;
               int k;
               if (grid[i][j] == 'W')
                  k = j + 1;
               else
                  k = j;
               for (; k < m && grid[i][k] != 'W'; k++) {
                  rowCnt += (grid[i][k] == 'E');
               }
            }
            if (!i || grid[i][j] == 'W') {
               colCnt[j] = 0;
               int k;
               if (grid[i][j] == 'W')
                  k = i + 1;
               else
                  k = i;
               for (; k < n && grid[k][j] != 'W'; k++) {
                  colCnt[j] += (grid[k][j] == 'E');
               }
            }
            if (grid[i][j] == '0') {
               ret = max(ret, rowCnt + colCnt[j]);
            }
         }
      }
      return ret;
   }
};
int main(){
   Solution ob;
   vector<vector<char>> v = {{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}};
   cout << (ob.maxKilledEnemies(v));
   return 0;
}

入力

{{'0','E','0','0'},{'E','0','W','E'},{'0','E','0','0'}}

出力

3