Pythonで爆弾の爆発時に安全なマスの数を求めるプログラム

2次元のバイナリ行列（0と1だけで構成された行列）を考えてみましょう。ここで、1は爆弾が置かれているセル、0は空のセルを表します。爆弾が爆発すると、その爆弾と同じ行および同じ列上にあるすべてのマスが被害を受けます。このとき、爆発の影響を受けずに安全に立てるマスの数を求めるのが課題です。

例えば、入力が以下のような行列だったとします。

この場合、出力は 2 になります。なぜなら、右下のセルと中央右のセルの2箇所だけが爆発の影響を受けない安全な場所だからです。

解き方のアプローチ

この問題は、以下の手順で効率よく解くことができます。

• r := 行列の行数と同じサイズのリストを作成し、すべて False で初期化する（各行に爆弾があるかどうかのフラグ）

• c := 行列の列数と同じサイズのリストを作成し、すべて False で初期化する（各列に爆弾があるかどうかのフラグ）

• i を 0 から行列の行数 - 1 まで繰り返す

  • j を 0 から行列の列数 - 1 まで繰り返す

    • matrix[i, j] が 1 の場合

      • r[i] := True、c[j] := True と設定する

• ct := 0（安全なマスのカウント用変数）

• 再度 i を 0 から行列の行数 - 1 まで繰り返す

  • j を 0 から行列の列数 - 1 まで繰り返す

    • r[i] が False かつ c[j] が False の場合

      • ct := ct + 1

• ct を返す

つまり、まず爆弾が存在する行と列をすべて記録し、その後「爆弾を含まない行」と「爆弾を含まない列」が交差するマスだけを数えればよいのです。計算量は O(行数 × 列数) となり、非常に効率的です。

それでは、実際の実装を見て理解を深めましょう。

サンプルコード

class Solution:
   def solve(self, matrix):
      r = [False for i in range(len(matrix))]
      c = [False for i in range(len(matrix[0]))]

      for i in range(len(matrix)):
         for j in range(len(matrix[0])):
            if matrix[i][j] == 1:
               r[i] = True
               c[j] = True

   ct = 0
   for i in range(len(matrix)):
      for j in range(len(matrix[0])):
         if r[i] == False and c[j] == False:
            ct += 1
   return ct

ob = Solution()
matrix = [
   [1, 1, 0],
   [0, 0, 0],
   [0, 0, 0]
]
print(ob.solve(matrix))

入力

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

出力

2