엔지니어 게시판
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.length
  • n == grid[i].length
  • 1 <= n <= 100
  • grid[i][j] is 0 or 1
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

        
전체 194 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


알림 0