数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究Python程序：查找距水域最远陆地的程序
假设我们有一个二进制矩阵，其中0代表水，1代表陆地。现在我们需要找到距水域曼哈顿距离最远的陆地，并最终返回该距离。
因此，如果输入如下所示：
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 |
则输出将为3，因为[0,0]单元格与水域的曼哈顿距离为3。
为了解决这个问题，我们将遵循以下步骤：
- 如果A为空，则
- 返回0
- R := 矩阵的行数，C := 矩阵的列数
- distance := 一个 R x C 阶矩阵，并填充0
- q := 一个双端队列，包含一些 (r, c) 对，其中 r 和 c 是矩阵的行和列索引，矩阵[r, c] 为 0
- 如果q的大小为0或R * C，则
- 返回-1
- 当q不为空时，执行以下操作：
- (r, c) := q 的左元素，然后从q中移除
- 对于[(r - 1, c) ,(r + 1, c) ,(r, c + 1) ,(r, c - 1) ]中的每个对(x, y)，执行以下操作：
- 如果x和y在矩阵范围内并且A[x, y]为1，则
- A[x, y] := 0
- distance[x, y] := distance[r, c] + 1
- 将(x, y)插入到q的末尾
- 如果x和y在矩阵范围内并且A[x, y]为1，则
- res := 一个包含每一行最大元素的列表
- 返回res的最大值
示例 (Python)
让我们来看下面的实现，以便更好地理解：
from collections import deque class Solution: def solve(self, A): if not A: return 0 R, C = len(A), len(A[0]) distance = [[0] * C for _ in range(R)] q = deque((r, c) for r in range(R) for c in range(C) if not A[r][c]) if len(q) in (0, R * C): return -1 while q: r, c = q.popleft() for x, y in [(r - 1, c), (r + 1, c), (r, c + 1), (r, c - 1)]: if 0 <= x < R and 0 <= y < C and A[x][y]: A[x][y] = 0 distance[x][y] = distance[r][c] + 1 q.append((x, y)) return max(max(row) for row in distance) ob = Solution() matrix = [ [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1], [0, 0, 1, 1] ] print(ob.solve(matrix))
输入
[ [1, 1, 1, 1], [1, 1, 0, 1], [1, 1, 1, 1], [0, 0, 1, 1] ]
输出
3
更新于：2020年12月12日
浏览量：137
广告