그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용

1368. 그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용

난이도:어려움

주제: 배열, 너비 우선 검색, 그래프, 힙(우선순위 큐), 행렬, 최단 경로

m x n 그리드가 주어졌습니다. 그리드의 각 셀에는 현재 이 셀에 있는 경우 방문해야 할 다음 셀을 가리키는 기호가 있습니다. 그리드[i][j]의 부호는 다음과 같습니다.

• 1은 오른쪽 셀로 이동한다는 의미입니다. (즉, 그리드[i][j]에서 그리드[i][j 1]로 이동)
• 2는 왼쪽 셀로 이동한다는 의미입니다. (즉, 그리드[i][j]에서 그리드[i][j - 1]로 이동)
• 3은 하위 셀로 이동한다는 의미입니다. (즉, 그리드[i][j]에서 그리드[i 1][j]로 이동)
• 4는 상위 셀로 이동한다는 의미입니다. (즉, 그리드[i][j]에서 그리드[i - 1][j]로 이동)

그리드 외부를 가리키는 그리드의 셀에 몇 가지 표시가 있을 수 있습니다.

처음에는 왼쪽 상단 셀(0, 0)에서 시작합니다. 그리드의 유효한 경로는 그리드의 기호를 따라 왼쪽 상단 셀(0, 0)에서 시작하여 오른쪽 하단 셀(m - 1, n - 1)에서 끝나는 경로입니다. 유효한 경로는 최단일 필요는 없습니다.

비용 = 1로 셀의 기호를 수정할 수 있습니다. 셀의 기호는 한 번만 수정할 수 있습니다.

그리드에 하나 이상의 유효한 경로가 있도록 만드는 데 드는 최소 비용을 반환합니다.

예 1:

• 입력: 그리드 = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2] ]
• 출력: 3
• 설명: (0, 0) 지점에서 시작합니다. (3, 3)의 경로는 다음과 같습니다. (0, 0) --> (0, 1) --> (0, 2) --> (0, 3)
• cost = 1 --> (1, 3) ---> (1, 2) ---> (1, 1) --> (1, 0)
• cost = 1 --> (2, 0) --> (2, 1) ---> (2, 2) ---> (2, 3)
• cost = 1 --> (3, 3) 총 비용 = 3.

예 2:

• 입력: 그리드 = [[1,1,3],[3,2,2],[1,1,4]]
• 출력: 0
• 설명: (0, 0)에서 (2, 2)까지의 경로를 따라갈 수 있습니다.

예 3:

• 입력: 그리드 = [[1,2],[4,3]]
• 출력: 1

제약조건:

• m == 그리드.길이
• n == 그리드[i].길이
• 1
• 1

힌트:

1. 그리드[i][j]가 가중치 간선을 사용하여 측면으로 인접한 4개의 셀 모두에 연결되는 그래프를 작성합니다. 가중치는 부호가 인접한 셀을 가리키면 0이고 그렇지 않으면 1입니다.
2. (0, 0)의 BFS를 먼저 가중치 = 0인 모든 간선을 방문합니다. 답은 (m -1, n - 1)까지의 거리입니다.

해결책:

0-1 BFS 접근 방식을 사용할 수 있습니다. 아이디어는 방향 수정 비용에 따라 셀이 deque의 앞 또는 뒤에 추가되는지 여부를 결정하는 deque(양단 큐)를 사용하여 그리드를 탐색하는 것입니다. 그리드는 현재 방향이 이웃 셀의 움직임과 일치하는지 여부에 따라 각 셀에 가중치가 부여된 가장자리가 있는 그래프로 처리됩니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 1368. 그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용

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

// Example Test Cases
$그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용 = [[1,1,1,1],[2,2,2,2],[1,1,1,1],[2,2,2,2]];
echo minCost($그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용) . "\n"; // Output: 3

$그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용 = [[1,1,3],[3,2,2],[1,1,4]];
echo minCost($그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용) . "\n"; // Output: 0

$그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용 = [[1,2],[4,3]];
echo minCost($그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용) . "\n"; // Output: 1
?>

설명:

1. 방향 매핑: 각 방향(오른쪽 1, 왼쪽 2, 아래쪽 3, 위쪽 4)은 이동 델타 [dx, dy] 배열에 매핑됩니다.

2. 0-1 BFS:

   • 데크는 비용이 낮은 셀의 우선순위를 지정하는 데 사용됩니다. 방향 수정이 필요하지 않은 셀은 앞쪽에 추가(unshift)되고, 수정이 필요한 셀은 뒤쪽(enqueue)에 추가됩니다.
   • 이렇게 하면 비용이 많이 드는 순서대로 세포가 처리됩니다.

3. 거리 배열: 2D 배열 $dist는 각 셀에 도달하는 데 필요한 최소 비용을 추적합니다. 시작 셀(0, 0)을 제외한 모든 셀에 대해 PHP_INT_MAX로 초기화됩니다.

4. 가장자리 가중치:

   • 현재 셀의 부호가 의도한 방향과 일치하면 비용은 동일하게 유지됩니다.
   • 그렇지 않으면 방향을 수정하면 1의 비용이 발생합니다.

5. 종료: 모든 셀이 처리되면 루프가 종료됩니다. 결과는 오른쪽 하단 모서리에 도달하는 데 필요한 최소 비용을 나타내는 $dist[$m - 1][$n - 1]의 값입니다.

복잡성:

• 시간 복잡도: O(m × n), 각 셀이 한 번씩 처리되기 때문입니다.
• 공간 복잡도: O(m × n), 거리 배열 및 데크의 경우

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 그리드에서 하나 이상의 유효한 경로를 만드는 데 드는 최소 비용의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!