그리드 게임

2017. 그리드게임

난이도:중

주제: 배열, 행렬, 접두사 합계

크기가 2 x n인 0 인덱스 2D 배열 그리드가 제공됩니다. 여기서 그리드[r][c]는 행렬의 (r, c) 위치에 있는 점 수를 나타냅니다. 두 로봇이 이 매트릭스에서 게임을 하고 있습니다.

두 로봇 모두 처음에는 (0, 0)에서 시작하여 (1, n-1)에 도달하려고 합니다. 각 로봇은 오른쪽((r, c)에서 (r, c 1)) 또는 아래((r, c)에서 (r 1, c))로만 이동할 수 있습니다.

게임 시작 시 첫 번째 로봇은 (0, 0)에서 (1, n-1)로 이동하여 경로에 있는 셀의 모든 포인트를 수집합니다. 경로를 통과하는 모든 셀(r, c)에 대해 그리드[r][c]는 0으로 설정됩니다. 그러면 두 번째 로봇은 (0, 0)에서 (1, n-1로 이동합니다. ) 경로에 있는 포인트를 수집합니다. 경로가 서로 교차할 수 있다는 점에 유의하세요.

첫 번째 로봇은 두 번째 로봇이 수집하는 포인트 수를 최소화하려고 합니다. 이와 대조적으로 두 번째 로봇은 자신이 수집하는 포인트 수를 최대화하려고 합니다. 두 로봇이 최적 플레이하면 두 번째 로봇이 수집한 점수를 반환합니다.

예 1:

• 입력: 그리드 = [[2,5,4],[1,5,1]]
• 출력: 4
• 설명: 첫 번째 로봇이 선택한 최적 경로는 빨간색으로 표시되고, 두 번째 로봇이 선택한 최적 경로는 파란색으로 표시됩니다.
  • 첫 번째 로봇이 방문한 셀은 0으로 설정됩니다.
  • 두 번째 로봇은 0 0 4 0 = 4점을 얻습니다.

예 2:

• 입력: 그리드 = [[3,3,1],[8,5,2]]
• 출력: 4
• 설명: 첫 번째 로봇이 선택한 최적 경로는 빨간색으로 표시되고, 두 번째 로봇이 선택한 최적 경로는 파란색으로 표시됩니다.
  • 첫 번째 로봇이 방문한 셀은 0으로 설정됩니다.
  • 두 번째 로봇은 0 3 1 0 = 4점을 얻습니다.

예 3:

• 입력: 그리드 = [[1,3,1,15],[1,3,3,1]]
• 출력: 7
• 설명: 첫 번째 로봇이 선택한 최적 경로는 빨간색으로 표시되고, 두 번째 로봇이 선택한 최적 경로는 파란색으로 표시됩니다.
  • 첫 번째 로봇이 방문한 셀은 0으로 설정됩니다.
  • 두 번째 로봇은 0 1 3 3 0 = 7점을 얻습니다.

제약조건:

• grid.length == 2
• n == 그리드[r].길이
• 1 4
• 1 5

힌트:

1. 첫 번째 로봇이 2열로 이동할 때 선택지는 n개입니다.
2. 접두사 합계를 사용하여 이 문제를 해결할 수 있나요?

해결책:

다음 접근 방식을 사용합니다.

1. 접두사 합계 계산: 모든 하위 배열의 점 합계를 효율적으로 계산하기 위해 그리드의 두 행에 대한 접두사 합계를 계산합니다.

2. 최적의 움직임 시뮬레이션:

   • 첫 번째 로봇은 두 번째 로봇에게 남은 포인트를 최소화하기 위해 경로를 결정합니다.
   • 각 열 전환에서 첫 번째 로봇은 아래로 이동하여 그리드를 두 세그먼트로 분할할 수 있습니다.
     • 상단 잔여 포인트: 전환 열 뒤 맨 위 행의 포인트
     • 남은 포인트: 전환 열 앞 하단 행에 있는 포인트

3. 두 번째 로봇의 최대 점수 최소화:

   • 각 전환마다 첫 번째 로봇의 경로 이후 두 번째 로봇이 수집할 수 있는 최대 포인트를 계산합니다.
   • 모든 전환에 걸쳐 최대값 중 최소값을 추적하세요.

이 솔루션을 PHP로 구현해 보겠습니다: 2017. 그리드게임

<?php function gridGame($grid) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage
$grid1 = [[2, 5, 4], [1, 5, 1]];
$grid2 = [[3, 3, 1], [8, 5, 2]];
$grid3 = [[1, 3, 1, 15], [1, 3, 3, 1]];

echo gridGame($grid1) . "\n"; // Output: 4
echo gridGame($grid2) . "\n"; // Output: 4
echo gridGame($grid3) . "\n"; // Output: 7
?>

설명:

1. 접두사 합계 계산:

   • prefixTop 및 prefixBottom은 각각 위쪽 행과 아래쪽 행의 누적 합계를 저장합니다.
   • 이를 통해 효율적인 범위 합계 계산이 가능합니다.

2. 최초의 로봇 경로 시뮬레이션:

   • 각 i 열에서 첫 번째 로봇은 i 열 다음으로 아래로 이동하기로 결정할 수 있습니다.
   • 이렇게 하면 그리드가 두 영역으로 분할됩니다.
     • i열 다음의 상단 행(수집 포인트: prefixTop[n] - prefixTop[i 1]).
     • i열 앞의 맨 아래 행(수집 포인트: prefixBottom[i]).

3. 두 번째 로봇의 최적점:

   • 두 번째 로봇은 남은 두 지역 중 최대 공간을 차지하게 됩니다.
   • 우리는 가능한 모든 전환에 대해 최대값 중 최소값을 추적합니다.

4. 복잡성:

   • 시간 복잡도: O(n), 접두사 합계를 계산하고 그리드를 한 번 반복합니다.
   • 공간 복잡도: O(n), 접두사 합 배열로 인해 발생

예제 연습

입력: 그리드 = [[2, 5, 4], [1, 5, 1]]

• 접두사 합계:
  • prefixTop = [0, 2, 7, 11]
  • prefixBottom = [0, 1, 6, 7]
• 전환 지점:
  • i = 0: 상단 남음 = 11 - 7 = 9, 하단 남음 = 0 → 두 번째 로봇 = 9.
  • i = 1: 상단 남음 = 11 - 11 = 4, 하단 남음 = 1 → 두 번째 로봇 = 4.
  • i = 2: 나머지 상단 = 0, 나머지 하단 = 6 → 두 번째 로봇 = 6.
• 두 번째 로봇의 최소 점수: min(9, 4, 6) = 4.

예상 출력과 일치합니다.

연락처 링크

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

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

• 링크드인
• 깃허브

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