数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python程序：查找可保持安全距离的最大k值
假设我们有一个二进制矩阵。其中0表示空单元格，1表示有人在的单元格。两个单元格之间的距离是x坐标差和y坐标差中的最大值。如果存在一个空正方形，其到矩阵中每个人的距离以及到矩阵每一侧的距离都大于或等于k，则该矩阵被认为是安全的，安全因子为k。我们需要找到可以保证安全的最大安全因子k。
例如，输入如下：
| 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 |
则输出为1，因为中间单元格到网格中每个人的距离至少为1。
为了解决这个问题，我们将遵循以下步骤：
N := A的尺寸
M := A[0]的尺寸
对于范围从0到N的i：
对于范围从0到M的j：
A[i, j] := A[i, j] XOR 1
ans := 0
对于范围从0到N的i：
对于范围从0到M的j：
如果i和j非零且A[i, j]为1，则：
A[i, j] := 1 + min(A[i - 1, j], A[i, j - 1], A[i - 1, j - 1])
ans = max(A[i, j], ans)
返回 (ans + 1) / 2
示例
让我们看看下面的实现以更好地理解：
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
更新于：2020-12-23
浏览量：118
广告