What is the best way to solve Walls And Gates?

The optimized O(n) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

벽과 문

'벽과 문' 문제에 대한 자세한 가이드 및 Python 구현.

문제 설명

쉬움

다음 세 가지 가능한 값으로 초기화된 m x n 그리드 룸이 제공됩니다.

- -1: 벽이나 장애물.

- 0: 게이트.

- INF(2147483647로 표현) : 빈 방.

각 빈 방을 가장 가까운 게이트까지의 거리로 채웁니다. Gate 도달이 불가능할 경우에는 INF로 채워야 한다.

수정된 방 그리드를 반환하는 wallsAndGates(rooms: List[List[int]]) -> List[List[int]] 함수를 작성하세요.

제약

•m == len(rooms)
•n == len(rooms[i])
•1 <= m, n <= 250
•rooms[i][j] is -1, 0, or 2147483647

예

Example 1

Input

rooms = [[2147483647,-1,0,2147483647],[2147483647,2147483647,2147483647,-1],[2147483647,-1,2147483647,-1],[0,-1,2147483647,2147483647]]

Output

[[3,-1,0,1],[2,2,1,-1],[1,-1,2,-1],[0,-1,3,4]]

Explanation

The empty rooms are filled with the shortest distance to their nearest gate.

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

from collections import deque
def walls_and_gates_opt(rooms):
    ROWS, COLS = len(rooms), len(rooms[0])
    q = deque()
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 0: q.append((r, c))
    while q:
        r, c = q.popleft()
        for dr, dc in [[1,0], [-1,0], [0,1], [0,-1]]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < ROWS and 0 <= nc < COLS and rooms[nr][nc] == 2147483647:
                rooms[nr][nc] = rooms[r][c] + 1
                q.append((nr, nc))

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def walls_and_gates_brute(rooms):
    ROWS, COLS = len(rooms), len(rooms[0])
    def dfs(r, c, dist):
        if r < 0 or r == ROWS or c < 0 or c == COLS or rooms[r][c] < dist:
            return
        rooms[r][c] = dist
        dfs(r + 1, c, dist + 1)
        dfs(r - 1, c, dist + 1)
        dfs(r, c + 1, dist + 1)
        dfs(r, c - 1, dist + 1)
    for r in range(ROWS):
        for c in range(COLS):
            if rooms[r][c] == 0:
                dfs(r, c, 0)