【leetcode】1162. As Far from Land as Possible
2024-09-02 08:49:01
题目如下:
Given an N x N
grid
containing only values0
and1
, where0
represents water and1
represents land, find a water cell such that its distance to the nearest land cell is maximized and return the distance.The distance used in this problem is the Manhattan distance: the distance between two cells
(x0, y0)
and(x1, y1)
is|x0 - x1| + |y0 - y1|
.If no land or water exists in the grid, return
-1
.Example 1:
Input: [[1,0,1],[0,0,0],[1,0,1]]
Output: 2
Explanation:
The cell (1, 1) is as far as possible from all the land with distance 2.Example 2:
Input: [[1,0,0],[0,0,0],[0,0,0]]
Output: 4
Explanation:
The cell (2, 2) is as far as possible from all the land with distance 4.Note:
1 <= grid.length == grid[0].length <= 100
grid[i][j]
is0
or1
解题思路:题目不难,注意用BFS,如果用DFS会超时。
代码如下:
class Solution(object):
def maxDistance(self, grid):
"""
:type grid: List[List[int]]
:rtype: int
"""
val = [[float('inf')] * len(grid[0]) for _ in grid]
queue = [] for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == 1:
queue.append((i, j, 0)) direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
while len(queue) > 0:
x, y, dis = queue.pop(0)
for (x1, y1) in direction:
if x + x1 >= 0 and x + x1 < len(grid) and y + y1 >= 0 \
and y + y1 < len(grid[0]) and grid[x + x1][y + y1] == 0 \
and val[x + x1][y + y1] > dis + 1:
val[x + x1][y + y1] = dis + 1
queue.append((x + x1, y + y1, dis + 1)) res = -1
for i in range(len(val)):
for j in range(len(val[i])):
if val[i][j] != float('inf') and res < val[i][j]:
res = val[i][j] return res
最新文章
- Java中的关键字 transient
- canvas 图片拖拽旋转之一——坐标转换translate
- 分享自制的13套 JQuery Mobile 界面主题(追加4套新款)
- DEV设计之自动流水号,DEV专家解答,自己折腾了半天也没有搞定,怪英文不好
- Eclipse+Tomcat+MAVEN+SVN项目完整环境搭建
- uiimageView连续帧动画
- codeforces GYM 100114 J. Computer Network 无相图缩点+树的直径
- windows相关小知识
- Competitive
- C# 隐藏文件
- Ubuntu 14.04 配置iptables防火墙
- bzoj 2618: [Cqoi2006]凸多边形 [半平面交]
- NLP︱LDA主题模型的应用难题、使用心得及从多元统计角度剖析
- Android 项目中用得最多最火的第三方框架可能都在这里了
- 转入墙内:SAS HBA crossflashing or flashing to IT mode, Dell Perc H200 and H310
- outline,box-shadow,border-radius小例子
- GIT好文搜藏
- Quartz小记(一):Elastic-Job - 分布式定时任务框架
- SonarQube 平台搭建代码审查平台步骤
- ofstream的使用方法--超级精细。C++文件写入、读出函数(转)
热门文章
- 【漏洞学习】slowHTTPtest 慢速 DOS 攻击方法 修复方案
- Selenium学习之==>;Selenium介绍
- 学习 Node.js 的 6 个步骤
- Java程序基本框架
- Unix时间戳和Java 的 System.currentTimeMillis()的区别
- C++类中的函数重载
- 卷积神经网络(ConvNets)中卷积的实现
- BZOJ 4033: [HAOI2015]树上染色题解
- 使用redis+flask维护动态代理池
- nodejs遍历文件夹下并操作HTML/CSS/JS/PNG/JPG