資料結構
網路
關係資料庫管理系統(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
廣告