JavaScriptで1つの爆弾で倒せる最大の敵の数を求めるアルゴリズム

問題の概要

2次元グリッドが与えられ、各セルは壁「W」、敵「E」、空きマス「0」(ゼロ)のいずれかです。この課題では、1つの爆弾を使って倒せる敵の最大数を返す関数を作成します。

爆弾は、設置した地点から同じ行と列に存在するすべての敵を倒します。ただし、壁は非常に強固で破壊できないため、爆発の効果は壁にぶつかった時点で止まります。

また、爆弾を設置できるのは空きマス「0」のみである点にも注意が必要です。

入力例と出力

たとえば、関数への入力が以下の場合を考えてみましょう。

const arr = [
    ['0', 'E', '0', '0'],
    ['E', '0', 'W', 'E'],
    ['0', 'E', '0', '0']
];

このとき、期待される出力は次の通りです。

const output = 3;

出力の解説

位置 [1, 1] に爆弾を設置すると、同じ行の左側にいる敵1体と、同じ列の上下にいる敵2体、合計3体の敵を倒すことができます。これがこのグリッドで達成できる最大値です。

効率的なアプローチ

各空きマスについて毎回行・列方向の敵を数え直す素朴な方法では、計算量が O(m²n²) になり非効率です。そこで、すでに数えた結果を再利用する考え方を取り入れます。

ポイントは次の2つです。

• 行方向: 行の先頭にいるか、直前のセルが壁「W」である場合に限り、その区間の敵の数を再カウントします。
• 列方向: 列ごとに配列 cols を用意し、列の先頭にいるか、真上のセルが壁である場合に限り再カウントします。

こうすることで各セルは一度ずつ処理するだけでよく、時間計算量は O(m × n) まで抑えられます。

コード実装

const arr = [
    ['0', 'E', '0', '0'],
    ['E', '0', 'W', 'E'],
    ['0', 'E', '0', '0']
];

const killEnemy = (arr = []) => {
    let m = arr.length;
    let n = m > 0 ? arr[0].length : 0;
    let result = 0, rows = 0;
    const cols = [];

    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            // 行の先頭、または左隣が壁なら行内の敵を再カウント
            if (j === 0 || arr[i][j-1] === 'W') {
                rows = 0;
                for (let k = j; k < n && arr[i][k] !== 'W'; ++k)
                    if (arr[i][k] === 'E')
                        rows += 1;
            }
            // 列の先頭、または真上が壁なら列内の敵を再カウント
            if (i === 0 || arr[i-1][j] === 'W') {
                cols[j] = 0;
                for (let k = i; k < m && arr[k][j] !== 'W'; ++k)
                    if (arr[k][j] === 'E')
                        cols[j] += 1;
            }
            // 空きマスなら、行+列の敵数の合計で最大値を更新
            if (arr[i][j] === '0' && rows + cols[j] > result)
                result = rows + cols[j];
        }
    }
    return result;
};

console.log(killEnemy(arr));

出力

コンソールには次のように表示されます。

3

まとめ

この問題は「Bomb Enemy」として知られる定番のアルゴリズム問題です。壁で区切られた区間ごとに行・列の敵数をキャッシュすることで、全マスを走査しても線形時間で答えを求められるのが大きなポイントです。必要な追加メモリも列数分の配列だけで済むため、空間計算量 O(n) と非常に効率的な実装になっています。