. 행렬

542. 01 매트릭스

난이도:중

주제: 배열, 동적 프로그래밍, 너비 우선 검색, 행렬

m x n 이진 행렬 매트가 주어지면 각 셀에 대해 가장 가까운 0의 거리를 반환합니다.

공통 모서리를 공유하는 두 셀 사이의 거리는 1입니다.

예 1:

• 입력: mat = [[0,0,0],[0,1,0],[0,0,0]]
• 출력: [[0,0,0],[0,1,0],[0,0,0]]

예 2:

• 입력: mat = [[0,0,0],[0,1,0],[1,1,1]]
• 출력: [[0,0,0],[0,1,0],[1,2,1]]

제약조건:

• m == mat.length
• n == mat[i].length
• 1 4
• 1 4
• mat[i][j]는 0 또는 1입니다.
• 매트에는 0이 하나 이상 있습니다.

참고: 이 질문은 1765년과 동일합니다. 최고봉 지도

해결책:

모든 0개의 셀이 시작점(소스)으로 처리되는 다중 소스 BFS(Breadth-First Search)를 사용하겠습니다. 1개의 셀마다 가장 가까운 0까지의 최소 거리를 계산합니다.

이 솔루션을 PHP로 구현해 보겠습니다. 542. 01 매트릭스

<?php /**
 * @param Integer[][] $mat
 * @return Integer[][]
 */
function updateMatrix($mat) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$mat1 = [[0,0,0],[0,1,0],[0,0,0]];
$mat2 = [[0,0,0],[0,1,0],[1,1,1]];

echo updateMatrix($mat1) . "\n"; // Output: [[0,0,0],[0,1,0],[0,0,0]]
echo updateMatrix($mat2) . "\n"; // Output: [[0,0,0],[0,1,0],[1,2,1]]
?>

설명:

1. 초기화:

   • 거리 배열은 처음에 모든 셀에 대해 PHP_INT_MAX로 초기화됩니다.
   • 0인 셀은 모두 거리 배열에서 0으로 설정되어 BFS 큐에 추가됩니다.

2. 멀티 소스 BFS:

   • 큐를 사용하여 모든 0개 셀에서 동시에 BFS를 수행합니다.
   • 큐의 각 셀에 대해 이웃(위, 아래, 왼쪽, 오른쪽)을 확인하세요.
   • 이웃의 거리를 줄일 수 있는 경우(distance[newRow][newCol] > currentDistance 1) 해당 거리를 업데이트하고 대기열에 추가합니다.

3. 출력:

   • 거리 배열은 모든 셀에 대해 가장 가까운 0에 대한 최소 거리로 업데이트됩니다.

입력 및 출력:

입력 1:

$mat1 = [
    [0, 0, 0],
    [0, 1, 0],
    [0, 0, 0]
];

출력 1:

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )
)

입력 2:

$mat2 = [
    [0, 0, 0],
    [0, 1, 0],
    [1, 1, 1]
];

출력 2:

Array
(
    [0] => Array
        (
            [0] => 0
            [1] => 0
            [2] => 0
        )

    [1] => Array
        (
            [0] => 0
            [1] => 1
            [2] => 0
        )

    [2] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 1
        )
)

이 솔루션은 각 셀이 한 번 처리되므로 O(m × n)의 시간 복잡도로 효율적입니다. 거리 배열과 BFS 큐로 인해 공간 복잡도도 O(m × n)입니다.

연락처 링크

이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!

이렇게 더 유용한 콘텐츠를 원하시면 저를 팔로우해주세요.

• 링크드인
• 깃허브

위 내용은 . 행렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!