Chương trình tìm số địa điểm an toàn khi bom nổ bằng Python?

Giả sử chúng ta có một ma trận nhị phân 2d, trong đó 1 đại diện cho một quả bom và 0 đại diện cho một ô trống. Khi một quả bom phát nổ, tất cả các khoảng trống trên cùng một hàng và cột đều bị hư hại. Chúng ta phải tìm số lượng không gian mà chúng ta có thể đứng để không bị hư hỏng.

Vì vậy, nếu đầu vào giống như

thì đầu ra sẽ là 2, vì có hai khoảng trống là ô dưới cùng bên phải và ô giữa bên phải là an toàn.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau:

• r:=một danh sách có kích thước giống như số hàng của ma trận và điền sai

• c:=một danh sách có kích thước giống như số cột của ma trận và điền sai

• đối với tôi trong phạm vi 0 đến số hàng của ma trận - 1, thực hiện

  • đối với j trong phạm vi 0 đến số cột của ma trận - 1, thực hiện

    • nếu ma trận [i, j] giống 1 thì

      • r [i]:=Đúng, c [j]:=Đúng

• ct:=0

• đối với tôi trong phạm vi 0 đến số hàng của ma trận - 1, thực hiện

  • đối với j trong phạm vi 0 đến số cột của ma trận - 1, thực hiện

    • nếu r [i] là Sai và c [j] là Sai thì

      • ct:=ct + 1

• trả lại ct

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn:

Ví dụ

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))

Đầu vào

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

Đầu ra

2