Chương trình tìm giá trị lớn nhất của k mà chúng ta có thể duy trì khoảng cách an toàn trong Python

Giả sử chúng ta có một ma trận nhị phân. Ở đây 0 biểu thị một ô trống và 1 biểu thị một ô có một người. Khoảng cách giữa hai ô là giá trị lớn nhất giữa chênh lệch tọa độ x và chênh lệch tọa độ y. Bây giờ ma trận được coi là an toàn với hệ số k nếu có một ô vuông trống sao cho khoảng cách từ ô đến mỗi người trong ma trận và mỗi cạnh của ma trận đều lớn hơn hoặc bằng k. Chúng ta phải tìm giá trị lớn nhất của hệ số k mà chúng ta có thể an toàn.

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

thì đầu ra sẽ là 1, vì ở ô giữa, khoảng cách từ ô đến mỗi người trong lưới ít nhất là 1.

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

• N:=kích thước của A

• M:=kích thước của A [0]

• đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện

  • đối với j trong phạm vi từ 0 đến M, thực hiện

    • A [i, j]:=A [i, j] XOR 1

• ans:=0

• đối với tôi trong phạm vi từ 0 đến N, hãy thực hiện

  • đối với j trong phạm vi từ 0 đến M, thực hiện

    • nếu i và j khác 0 và A [i, j] là 1 thì

      • A [i, j]:=1 + tối thiểu A [i - 1, j], A [i, j - 1] và A [i - 1, j - 1]

      • ans =tối đa A [i, j] và ans

• return (ans + 1) / 2

Ví dụ

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

class Solution:
def solve(self, A):
   N = len(A)
   M = len(A[0])
   for i in range(N):
      for j in range(M):
         A[i][j] ^= 1
   ans = 0
   for i in range(N):
      for j in range(M):
         if i and j and A[i][j]:
            A[i][j] = 1 + min(A[i - 1][j], A[i][j - 1], A[i - 1][j - 1])
            ans = max(A[i][j], ans)
   return (ans + 1) // 2
ob = Solution()
matrix = [
   [0, 0, 0, 0, 0],
   [0, 1, 1, 1, 0],
   [0, 1, 0, 1, 0],
   [0, 1, 1, 1, 0],
   [0, 0, 0, 0, 0],
]
print(ob.solve(matrix))

Đầu vào

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

Đầu ra

1