Python程序：查找我们可以保持安全距离的最大k值

假设我们有一个二进制矩阵。在这里，0表示一个空单元格，1表示具有一个人的单元格。两个单元格之间的距离是x坐标差和y坐标差之间的最大值。现在，如果存在一个空方块，这个方块到矩阵中的每个人员和矩阵的每个边缘的距离都大于或等于k，则认为矩阵是安全的。我们必须找到我们可以安全的最大因素k的值。

因此，如果输入如下所示，则输出将为1，因为在中间单元格中，该单元格到网格中的每个人员的距离至少为1。

0	0	0	0	0
0	1	0	1	0
0	1	1	1	0
0	1	1	1	0
0	0	0	0	0

为了解决这个问题，我们将遵循以下步骤：

• N := A的大小

• M := A [0]的大小

• for i in range 0 to N, do

  • for j in range 0 to M, do
    • A [i，j]：= A [i，j] XOR 1
• ans := 0

• for i in range 0 to N, do

  • for j in range 0 to M, do
    • 如果i和j都不为零且A [i，j]为1，则

    • A [i，j]：= 1 + A [i-1，j]，A [i，j-1]和A [i-1，j-1]的最小值

    • ans = max（A [i，j]和ans ）

• 返回（ans + 1）/ 2

更多Python相关文章，请阅读：Python 教程

示例

我们看一下以下实现，以便更好的理解 –

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

输入

[
   [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],
]

输出

1