찾다

그리드 게임

Jan 22, 2025 am 02:02 AM

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
세션과 관련된 크로스 사이트 스크립팅 (XSS) 공격으로부터 어떻게 보호 할 수 있습니까?세션과 관련된 크로스 사이트 스크립팅 (XSS) 공격으로부터 어떻게 보호 할 수 있습니까?Apr 23, 2025 am 12:16 AM

세션 관련 XSS 공격으로부터 응용 프로그램을 보호하려면 다음 조치가 필요합니다. 1. 세션 쿠키를 보호하기 위해 Httponly 및 Secure 플래그를 설정하십시오. 2. 모든 사용자 입력에 대한 내보내기 코드. 3. 스크립트 소스를 제한하기 위해 컨텐츠 보안 정책 (CSP)을 구현하십시오. 이러한 정책을 통해 세션 관련 XSS 공격을 효과적으로 보호 할 수 있으며 사용자 데이터가 보장 될 수 있습니다.

PHP 세션 성능을 어떻게 최적화 할 수 있습니까?PHP 세션 성능을 어떻게 최적화 할 수 있습니까?Apr 23, 2025 am 12:13 AM

PHP 세션 성능을 최적화하는 방법 : 1. 지연 세션 시작, 2. 데이터베이스를 사용하여 세션을 저장, 3. 세션 데이터 압축, 4. 세션 수명주기 관리 및 5. 세션 공유 구현. 이러한 전략은 높은 동시성 환경에서 응용의 효율성을 크게 향상시킬 수 있습니다.

SESSION.GC_MAXLIFETIME 구성 설정은 무엇입니까?SESSION.GC_MAXLIFETIME 구성 설정은 무엇입니까?Apr 23, 2025 am 12:10 AM

THESESSION.GC_MAXLIFETIMESETTINGINSTTINGTINGSTINGTERMINESTERMINESTERSTINGSESSIONDATA, SETINSECONDS.1) IT'SCONFIGUDEDINPHP.INIORVIAINI_SET ()

PHP에서 세션 이름을 어떻게 구성합니까?PHP에서 세션 이름을 어떻게 구성합니까?Apr 23, 2025 am 12:08 AM

PHP에서는 Session_Name () 함수를 사용하여 세션 이름을 구성 할 수 있습니다. 특정 단계는 다음과 같습니다. 1. Session_Name () 함수를 사용하여 Session_Name ( "my_session")과 같은 세션 이름을 설정하십시오. 2. 세션 이름을 설정 한 후 세션을 시작하여 세션을 시작하십시오. 세션 이름을 구성하면 여러 응용 프로그램 간의 세션 데이터 충돌을 피하고 보안을 향상시킬 수 있지만 세션 이름의 독창성, 보안, 길이 및 설정 타이밍에주의를 기울일 수 있습니다.

세션 ID를 얼마나 자주 재생해야합니까?세션 ID를 얼마나 자주 재생해야합니까?Apr 23, 2025 am 12:03 AM

세션 ID는 로그인시, 민감한 작업 전에 및 30 분마다 정기적으로 재생되어야합니다. 1. 세션 고정 공격을 방지하기 위해 로그인 할 때 세션 ID를 재생합니다. 2. 안전성을 향상시키기 위해 민감한 작업 전에 재생성. 3. 정기적 인 재생은 장기 활용 위험을 줄이지 만 사용자 경험을 평가해야합니다.

PHP에서 세션 쿠키 매개 변수를 어떻게 설정합니까?PHP에서 세션 쿠키 매개 변수를 어떻게 설정합니까?Apr 22, 2025 pm 05:33 PM

Session_SET_COOKIE_PARAMS () 함수를 통해 PHP에서 세션 쿠키 매개 변수 설정을 달성 할 수 있습니다. 1)이 기능을 사용하여 만료 시간, 경로, 도메인 이름, 보안 플래그 등과 같은 매개 변수를 설정하십시오. 2) call session_start ()를 호출하려면 매개 변수를 발효시킵니다. 3) 사용자 로그인 상태와 같은 요구에 따라 매개 변수를 동적으로 조정합니다. 4) 보안을 향상시키기 위해 안전하고 httponly 플래그 설정에주의를 기울이십시오.

PHP에서 세션을 사용하는 주요 목적은 무엇입니까?PHP에서 세션을 사용하는 주요 목적은 무엇입니까?Apr 22, 2025 pm 05:25 PM

PHP에서 세션을 사용하는 주요 목적은 다른 페이지간에 사용자의 상태를 유지하는 것입니다. 1) 세션은 Session_Start () 함수를 통해 시작되어 고유 한 세션 ID를 생성하고 사용자 쿠키에 저장합니다. 2) 세션 데이터는 서버에 저장되므로 로그인 상태 및 쇼핑 카트 컨텐츠와 같은 다른 요청간에 데이터를 전달할 수 있습니다.

하위 도메인에서 세션을 어떻게 공유 할 수 있습니까?하위 도메인에서 세션을 어떻게 공유 할 수 있습니까?Apr 22, 2025 pm 05:21 PM

하위 도메인 간의 세션을 공유하는 방법? 공통 도메인 이름에 대한 세션 쿠키를 설정하여 구현. 1. 세션 쿠키 도메인을 서버 측에서 .example.com으로 설정하십시오. 2. 메모리, 데이터베이스 또는 분산 캐시와 같은 적절한 세션 저장 방법을 선택하십시오. 3. 쿠키를 통해 세션 ID를 전달하면 서버는 ID를 기반으로 세션 데이터를 검색하고 업데이트합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

Video Face Swap

Video Face Swap

완전히 무료인 AI 얼굴 교환 도구를 사용하여 모든 비디오의 얼굴을 쉽게 바꾸세요!

뜨거운 도구

SublimeText3 Mac 버전

SublimeText3 Mac 버전

신 수준의 코드 편집 소프트웨어(SublimeText3)

안전한 시험 브라우저

안전한 시험 브라우저

안전한 시험 브라우저는 온라인 시험을 안전하게 치르기 위한 보안 브라우저 환경입니다. 이 소프트웨어는 모든 컴퓨터를 안전한 워크스테이션으로 바꿔줍니다. 이는 모든 유틸리티에 대한 액세스를 제어하고 학생들이 승인되지 않은 리소스를 사용하는 것을 방지합니다.

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기

에디트플러스 중국어 크랙 버전

에디트플러스 중국어 크랙 버전

작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음

SecList

SecList

SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.