Pythonで行列上の爆弾ですべての敵を倒せるかどうかを判定する方法

ここでは、行列 mat が与えられたとき、そのセルには次の3種類の値が格納されているものとします。

• 0: 空きエリア
• 1: 爆弾
• 2: 敵

爆弾は、上下左右(水平・垂直方向)の一端からもう一端まで爆発して範囲内を破壊します。このとき、すべての敵が爆発によって倒されるかどうかを判定するのが本記事の目的です。

問題の例

たとえば、次のような入力が与えられたとします。

この場合の出力は True になります。その理由は以下の通りです。

• 位置 [1, 1] の爆弾が縦方向に爆発し、位置 [2, 1] の敵を倒します。
• 位置 [3, 2] の爆弾が縦方向に爆発し、位置 [0, 2] の敵を倒します。

結果として、すべての敵が爆発の範囲内に含まれるため、答えは True となります。

解決のためのアルゴリズム

この問題は、次の手順で解くことができます。

1. r := 行列 mat の行数、c := 列数 を取得します。
2. すべてのセルを走査し、値が 1(爆弾)であるセルを見つけます。
3. 爆弾が見つかったら、その列全体と行全体に対して、爆弾以外のセル(敵や空きエリア)をすべて 0 に書き換えます。これにより爆発の影響範囲を表現できます。
4. すべての爆弾について処理が完了したら、再度行列を走査します。
5. まだ値が 2(敵)として残っているセルが存在すれば False を返します。
6. 敵がひとつも残っていなければ True を返します。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

def solve(mat):
    r = len(mat)
    c = len(mat[0])
    i, j, x, y = 0, 0, 0, 0
    for i in range(r):
        for j in range(c):
            if mat[i][j] == 1:
                for x in range(r):
                    if mat[x][j] != 1:
                        mat[x][j] = 0
                for y in range(c):
                    if mat[i][y] != 1:
                        mat[i][y] = 0
    for i in range(r):
        for j in range(c):
            if mat[i][j] == 2:
                return False
    return True

matrix = [ [0,0,2,0], [0,1,0,0], [0,2,0,0], [0,0,1,0] ]
print(solve(matrix))

入力

[
[0,0,2,0],
[0,1,0,0],
[0,2,0,0],
[0,0,1,0]
]

出力

True

コードのポイント

• 最初の二重ループで爆弾(1)の位置を検出し、その行・列を順に 0 で埋めていくことで「爆発済み」の状態を再現しています。
• 爆弾自体(値が 1 のセル)は上書きしないため、複数の爆弾が同じ行・列にある場合でも正しく処理されます。
• 最後にもう一度行列を走査し、敵(2)が残っていないかを確認することで判定を行います。

このように、爆発の影響範囲をシミュレートしてから残存する敵の有無を確認するというシンプルなアプローチで、問題を効率的に解くことができます。