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

난이도 : hard

당신은 비 음성 정수로 구성된 m x n 매트릭스 그리드가 주어집니다.

th 두 번째 매트릭스의 상단 왼쪽 셀에 서서 인접한 셀로 이동해야합니다 : 위, 아래, 왼쪽 및 오른쪽. 당신이 만드는 각각의 움직임은 1 초가 걸립니다.

return Matrix의 바닥 오른쪽 셀을 방문 할 수있는 최소 ^{필요한 시간입니다. 오른쪽 하단 셀을 방문 할 수 없다면 -1} . 를 반환합니다.

입력 : grid = [[0,1,3,2], [5,1,2,5], [4,3,8,6]

출력 :

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

입력 : grid = [[0,2,4], [3,2,1], [1,0,4]

출력 :

• 설명 : 왼쪽 상단에서 오른쪽 바닥까지의 경로가 없습니다.
• 제약 조건 :
• m == grid.length

2

• 0 sup> 5
• 그리드 [0] [0] == 0
• 힌트:
• 그래프에서 가장 짧은 경로를 찾을 수있는 알고리즘을 사용해보십시오.

우리는
2. dijkstra 알고리즘
의 수정 된 버전을

를 사용하여 적용 할 수 있습니다. 이 문제는 본질적으로 왼쪽 상단 셀에서 바닥 오른쪽 셀을 방문하는 데 필요한 가장 짧은 시간을 찾도록 요청합니다. 여기서 각 움직임은 그리드의 값을 기반으로 시간 제약 조건이 있습니다. 접근하다:

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

1. 우선 순위 큐 (Min-Heap)

   : 우선 순위 큐를 사용하여 항상 필요한 시간이 가장 적은 셀을 탐색하십시오. 이것은 우리가 그들을 도달 할 수있는 초기의 순서대로 세포를 처리하고 있습니다.

2. 수정 된 bfs

   : 각 셀에 대해 인접한 셀로 이동할 수 있는지 확인하고 방문 할 수있는 시간을 업데이트 할 수 있는지 확인합니다. 셀이 전류보다 나중에 방문되면 새로운 시간과 함께 대기열에 다시 추가합니다.

3. Early Exit

   : 일단 오른쪽 셀에 도달하면 시간을 반환 할 수 있습니다. 큐에 도달하지 않고 대기열을 배출하면 -1.

PHP 에서이 솔루션을 구현하겠습니다 :
4. 2577. 그리드에서 셀을 방문하는 최소 시간
   php /** * @param integer [] [] $ 그리드 * @return Integer */ 함수 최소 시간 ($ 그리드) { ... ... ... /** * ./solution.php로 이동하십시오 */ } // 예 1 $ grid1 = [ [0, 1, 3, 2], [5, 1, 2, 5], [4, 3, 8, 6] ]; 에코 최소 시간 ($ grid1). php_eol; // 출력 : 7 // 예제 2 $ grid2 = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; 에코 최소 시간 ($ grid2). php_eol; // 출력 : -1 ?>

파골 리티 큐는 최소 시간을 가진 셀이 먼저 처리되도록하는 데 사용됩니다. PHP의 SpliorityQueue가 기본적으로 최대 eap이기 때문에 우선 순위는 -time으로 저장됩니다.

1. Traversal :
   
   상단 왼쪽 셀 (0, 0)에서 시작하여, 알고리즘은 가장 초기 시간을 방문 할 수있는 모든 도달 가능한 셀을 처리합니다 (Max (0, 그리드 [Newrow] [NewCol] - (시간 1))).

2. 방문한 세포
   :
   

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

3. 경계 및 유효성 검사
   :
   

   알고리즘은 그리드의 범위 내에 머무르고 유효한 이웃 만 처리 할 수 ​​있도록합니다.

4. 시간 계산
   :
   

   각 움직임은 1 초가 걸리고 셀에 대기가 필요한 경우 (예 : 그리드 [Newrow] [NewCol]> Time 1) 필요한 시간까지 알고리즘이 기다립니다.

5. 엣지 케이스
   :
   

   대기열이 소진되고 바닥 오른쪽 셀에 도달하지 않으면 함수는 -1.

6. 복잡성 분석
   
   

각 셀이 우선 순위 큐에 최대 한 번에 추가됩니다 :

1. o (m x n x log (m x n))

   m
   • n

2. • 공간 복잡성 : 우선 순위 대기열과 방문한 배열의 공간은
   o (m x n)

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

입력:

$grid = [
    [0, 2, 4],
    [3, 2, 1],
    [1, 0, 4]
];
echo minimumTime($grid); // Output: -1

입력:

$ grid = [ [0, 2, 4], [3, 2, 1], [1, 0, 4] ]; 에코 최소 시간 ($ 그리드); // 출력 : -1 이 솔루션은 효율적이며 제약 조건 내에서 잘 작동합니다.

연락처 링크

이 시리즈가 도움이된다면

Github의 스타를 제공하거나 좋아하는 소셜 네트워크에 게시물을 공유하는 것이 좋습니다. 당신의 지원은 나에게 큰 의미가 있습니다!
• 이와 같은 유용한 컨텐츠를 원한다면 언제든지 나중하십시오 :
• linkedin