그리드의 셀을 방문하는 최소 시간

2577. 그리드의 셀을 방문하는 최소 시간

난이도:어려움

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

음수가 아닌 정수로 구성된 m x n 행렬 그리드가 제공됩니다. 여기서 그리드[행][col]은 셀(행, col), 이는 셀(행, 열)을 방문하는 시간이 그리드[행][col]보다 크거나 같은 경우에만 셀(행, 열)을 방문할 수 있음을 의미합니다. 당신은 0

번째

초 행렬의 왼쪽 위 셀에 서 있고, 4개 중 ^아무인접 셀로 이동해야 합니다. 방향: 위, 아래, 왼쪽, 오른쪽. 각 동작에는 1초가 소요됩니다. 행렬의 오른쪽 하단 셀을 방문하는 데 필요한

최소

시간을 반환합니다. 오른쪽 하단 셀을 방문할 수 없으면 -1을 반환합니다.

예 1:

입력:
• 그리드 = [[0,1,3,2],[5,1,2,5],[4,3,8,6]]
출력:
• 7
설명:
• 우리가 취할 수 있는 경로 중 하나는 다음과 같습니다. t = 0에서 셀(0,0)에 있습니다.
  • t = 1에서 셀(0,1)로 이동합니다. 그리드[0][1] <= 1이기 때문에 가능합니다.
  • t = 2에서 셀 (1,1)로 이동합니다. 그리드[1][1] <= 2이기 때문에 가능합니다.
  • t = 3에서 셀(1,2)로 이동합니다. 그리드[1][2] <= 3이기 때문에 가능합니다.
  • t = 4에서 셀 (1,1)로 이동합니다. 그리드[1][1] <= 4이기 때문에 가능합니다.
  • t = 5에서 셀(1,2)로 이동합니다. 그리드[1][2] <= 5이기 때문에 가능합니다.
  • t = 6에서 셀(1,3)으로 이동합니다. 그리드[1][3] <= 6이기 때문에 가능합니다.
  • t = 7에서 셀(2,3)으로 이동합니다. 그리드[2][3] <= 7이기 때문에 가능합니다.
  • 마지막 시간은 7시입니다. 가능한 최소 시간이라고 볼 수 있습니다.

예 2:

입력:
• 그리드 = [[0,2,4],[3,2,1],[1,0,4]]
출력:
• -1
설명:
• 왼쪽 상단에서 오른쪽 하단 셀까지 경로가 없습니다.

제약조건:

m == 그리드.길이

• n == 그리드[i].길이
• 2 <= m, n <= 1000
• 4 <= m * n <= 10>sup>5
• 0 <= 그리드[i][j] <= 10>sup>5
• 그리드[0][0] == 0

힌트:

1. 그래프에서 최단 경로를 찾을 수 있는 알고리즘을 사용해 보세요.
2. 다른 셀의 잠금을 해제하기 위해 매트릭스의 두 셀 사이를 왔다 갔다 해야 하는 경우를 생각해 보세요.

해결책:

우선순위 대기열을 사용하여 다익스트라 알고리즘의 수정된 버전을 적용할 수 있습니다. 이 문제는 본질적으로 왼쪽 상단 셀에서 오른쪽 하단 셀을 방문하는 데 필요한 최단 시간을 찾도록 요구합니다. 여기서 각 이동은 그리드의 값에 따라 시간 제약이 있습니다.

접근하다:

1. 그래프 표현: 그리드의 각 셀을 노드로 처리합니다. 가장자리는 이동할 수 있는 인접한 셀(위, 아래, 왼쪽, 오른쪽)입니다.

2. 우선순위 큐(최소 힙): 우선순위 큐를 사용하면 항상 최소한의 시간으로 셀을 탐색할 수 있습니다. 이렇게 하면 가장 빠른 시간에 도달할 수 있는 순서대로 셀을 처리할 수 있습니다.

3. 수정된 BFS: 각 셀에 대해 인접한 셀로 이동할 수 있는지 확인하고 방문할 수 있는 시간을 업데이트합니다. 현재보다 늦은 시간에 셀을 방문하면 새로운 시간으로 큐에 다시 추가됩니다.

4. 조기 종료: 오른쪽 하단 셀에 도달하면 시간을 반환할 수 있습니다. 대기열에 도달하지 않고 대기열을 소진하면 -1을 반환합니다.

PHP에서 이 솔루션을 구현해 보겠습니다: 2577. 그리드의 셀을 방문하는 최소 시간

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

설명:

1. 우선순위 대기열:
   
   SplPriorityQueue는 최소 시간을 가진 셀이 먼저 처리되도록 하는 데 사용됩니다. PHP의 SplPriorityQueue는 기본적으로 최대 힙이므로 우선순위는 -time으로 저장됩니다.

2. 순회:
   
   알고리즘은 왼쪽 상단 셀(0, 0)부터 시작하여 각 셀을 방문할 수 있는 가장 빠른 시간(max(0,grid[newRow][newCol] - (time 1)))을 고려하여 도달 가능한 모든 셀을 처리합니다.

3. 방문한 셀:
   
   방문 배열은 중복 계산과 무한 루프를 피하기 위해 이미 처리된 셀을 추적합니다.

4. 경계 및 유효성 검사:
   
   알고리즘은 그리드 경계 내에 머무르고 유효한 이웃만 처리하도록 보장합니다.

5. 시간 계산:
   
   각 이동에는 1초가 걸리며, 셀에 대기가 필요한 경우(예: Grid[newRow][newCol] > 시간 1) 알고리즘은 필요한 시간까지 기다립니다.

6. 엣지 케이스:
   
   대기열이 소진되고 오른쪽 하단 셀에 도달하지 못한 경우 함수는 -1을 반환합니다.

---

복잡성 분석

1. 시간 복잡성:

   • 각 셀은 최대 한 번 우선순위 대기열에 추가됩니다. O(m x n x log(m x n)), 여기서 m 및 n은 그리드입니다. 크기입니다.

2. 공간 복잡성:

   • 우선순위 큐와 방문 배열의 공간은 O(m x n).
   입니다.

---

예제 실행

입력:

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

// Example 1
$grid1 = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid1) . PHP_EOL; // Output: 7

// Example 2
$grid2 = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid2) . PHP_EOL; // Output: -1
?>

입력:

$grid = [
    [0, 1, 3, 2],
    [5, 1, 2, 5],
    [4, 3, 8, 6]
];
echo minimumTime($grid); // Output: 7

이 솔루션은 효율적이며 제약 조건 내에서 잘 작동합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

위 내용은 그리드의 셀을 방문하는 최소 시간의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!