Pythonで爆弾が爆発したときに安全な場所の数を見つけるプログラムはありますか？

2次元のバイナリ行列があるとします。ここで、1は爆弾を表し、0は空のセルを表します。爆弾が爆発すると、同じ行と列に沿ったすべてのスペースが損傷します。ダメージを受けないように立つことができるスペースの数を見つける必要があります。

したがって、入力が次のような場合

右下のセルと右中央のセルに2つのスペースがあるため、出力は2になります。

これを解決するには、次の手順に従います。

• r：=行列の行数と同じサイズのリストで、falseで埋める

• c：=行列の列数と同じサイズのリストで、falseで埋める

• 範囲0から行列の行数-1までのiの場合、実行

  • 0から行列の列数までの範囲のjの場合-1、do

    • matrix [i、j]が1と同じ場合、

      • r [i]：=True、c [j]：=True

• ct：=0

• 範囲0から行列の行数-1までのiの場合、実行

  • 0から行列の列数までの範囲のjの場合-1、do

    • r [i]がFalseで、c [j]がFalseの場合、

      • ct：=ct + 1

• ctを返す

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

例

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