LeetCode 솔루션 분류
[2/10] 1162. As Far from Land as Possible
본문
Given an n x n grid containing only values 0 and 1, where 0 represents water and 1 represents land, find a water cell such that its distance to the nearest land cell is maximized, and return the distance. If no land or water exists in the grid, return -1.
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|.
Example 1:
Input: grid = [[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: grid = [[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.
Constraints:
n == grid.lengthn == grid[i].length1 <= n <= 100grid[i][j]is0or1
Accepted
97.4K
Submissions
196.1K
Acceptance Rate
49.7%
관련자료
-
링크
댓글 1
학부유학생님의 댓글
- 익명
- 작성일
from collections import deque
class Solution:
def maxDistance(self, grid: List[List[int]]) -> int:
ROW, COL = len(grid), len(grid[0])
directions = [(1,0),(0,1),(-1,0), (0,-1)]
dq = deque([(r,c) for c in range(COL) for r in range(ROW) if grid[r][c]])
maxdis = 0
while dq:
r, c = dq.popleft()
for rd, cd in directions:
nr, nc = r+rd, c+cd
if 0<=nr<ROW and 0<=nc<COL and grid[nr][nc] == 0:
dq.append((nr,nc))
grid[nr][nc] = grid[r][c] + 1
maxdis = max(maxdis, grid[nr][nc])
return maxdis - 1
