>  기사  >  백엔드 개발  >  . 걷는 로봇 시뮬레이션

. 걷는 로봇 시뮬레이션

PHPz
PHPz원래의
2024-09-05 06:47:08532검색

. Walking Robot Simulation

874. 걷는 로봇 시뮬레이션

난이도:

주제: 배열, 해시 테이블, 시뮬레이션

무한한 XY 평면 위의 로봇은 북쪽을 향한 지점 (0, 0)에서 시작합니다. 로봇은 다음 세 가지 가능한 명령 유형을 순서대로 수신할 수 있습니다.

  • -2: 좌회전 90도.
  • -1: 우회전 90도.
  • 1

그리드 사각형 중 일부는 장애물입니다. i번째 장애물은 그리드 포인트 장애물[i] = (xi, yi)에 있습니다. 로봇이 장애물에 부딪히면 대신 현재 위치에 머무르며 다음 명령으로 이동합니다.

로봇이 원점 제곱에서 얻은 최대 유클리드 거리를 반환합니다(즉, 거리가 5이면 25를 반환합니다).

참고:

  • 북쪽은 +Y 방향을 의미합니다.
  • 동쪽은 +X 방향을 의미합니다.
  • 남쪽은 -Y 방향을 의미합니다.
  • 서쪽은 -X 방향을 의미합니다.
  • [0,0]에 장애물이 있을 수 있습니다.

예 1:

  • 입력: 명령 = [4,-1,3], 장애물 = []
  • 출력: 25
  • 설명: 로봇은 (0, 0)에서 시작합니다.
    1. 북쪽으로 4단위를 (0, 4)로 이동하세요.
    2. 우회전.
    3. 동쪽으로 3단위를 (3, 4)로 이동하세요.
    4. 로봇이 원점에서 가장 먼 지점은 (3, 4)이며, 이 값의 제곱은 32 + 42 = 25단위입니다.

예 2:

  • 입력: 명령 = [4,-1,4,-2,4], 장애물 = [[2,4]]
  • 출력: 65
  • 설명: 로봇은 (0, 0)에서 시작합니다.
    1. 북쪽으로 4단위를 (0, 4)로 이동하세요.
    2. 우회전.
    3. 동쪽으로 1칸 이동 후 (2, 4)의 장애물에 막히면 ​​로봇은 (1, 4)에 있습니다.
    4. 좌회전하세요.
    5. 북쪽으로 4칸을 (1, 8)로 이동하세요.
    6. 로봇이 원점에서 가장 먼 지점은 (1, 8)이며, 이 값의 제곱은 12 + 82 = 65단위입니다.

예 3:

  • 입력: 명령 = [6,-1,-1,6], 장애물 = []
  • 출력: 36
  • 설명: 로봇은 (0, 0)에서 시작합니다.
    1. 북쪽으로 6단위를 (0, 6)으로 이동하세요.
    2. 우회전.
    3. 우회전.
    4. 남쪽으로 6단위 이동하여 (0, 0)으로 이동합니다.
    5. 로봇이 원점에서 가장 먼 지점은 (0, 6)이며, 이 값의 제곱은 62 = 36 단위 떨어져 있습니다.

제약조건:

  • 1 <= Commands.length <= 104
  • 명령[i]은 -2, -1 또는 [1, 9] 범위의 정수입니다.
  • 0 <= 장애물.길이 <= 104
  • -3 * 104 <= xi, yi <= 3 * 104
  • 답은 2 미만이 보장됩니다31

해결책:

우리는 일련의 명령을 기반으로 무한한 2D 그리드에서 로봇의 움직임을 시뮬레이션하고 장애물이 있는 경우 피해야 합니다. 목표는 로봇이 원점에서 도달하는 최대 유클리드 거리의 제곱을 구하는 것입니다.

접근하다

  1. 방향 처리:

    • 로봇은 동서남북 4방향 중 하나를 향할 수 있습니다.
    • 이러한 방향을 벡터로 나타낼 수 있습니다.
      • 북쪽: (0, 1)
      • 동쪽: (1, 0)
      • 남쪽: (0, -1)
      • 서쪽: (-1, 0)
  2. 회전:

    • 좌회전(-2)하면 방향이 시계 반대 방향으로 90도 이동합니다.
    • 우회전(-1)하면 방향이 시계 방향으로 90도 이동합니다.
  3. 이동:

    • 각 이동 명령에 대해 로봇은 한 번에 한 유닛씩 현재 방향으로 이동합니다. 장애물을 만나면 해당 명령에 따라 이동을 멈춥니다.
  4. 장애물 추적:

    • 빠른 조회를 위해 장애물 목록을 튜플 세트로 변환하면 로봇이 장애물에 부딪힐지 빠르게 판단할 수 있습니다.
  5. 거리 계산:

    • 로봇이 이동 중 도달하는 원점에서 최대 거리의 제곱을 추적합니다.

이 솔루션을 PHP로 구현해 보겠습니다: 874. 걷는 로봇 시뮬레이션






설명:

  • 방향 관리: 벡터 목록을 사용하여 방향을 나타내므로 이동 후 다음 위치를 쉽게 계산할 수 있습니다.
  • 장애물 감지: 장애물을 세트로 저장하여 위치가 장애물에 의해 차단되었는지 확인하는 데 O(1) 시간 복잡도를 달성합니다.
  • 거리 계산: 로봇이 이동하면서 도달하는 최대 제곱 거리를 지속적으로 업데이트합니다.

테스트 케이스

  • 제공된 예제 테스트 사례는 솔루션을 검증하는 데 사용됩니다.
    • 장애물이 없는 [4,-1,3]은 25를 반환해야 합니다.
    • 장애물 [[2,4]]가 있는 [4,-1,4,-2,4]는 65를 반환해야 합니다.
    • 장애물이 없는 [6,-1,-1,6]은 36을 반환해야 합니다.

이 솔루션은 문제 제약 조건을 효율적으로 처리하고 필요에 따라 최대 거리의 제곱을 계산합니다.

연락처 링크

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

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

  • 링크드인
  • 깃허브

위 내용은 . 걷는 로봇 시뮬레이션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명:
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.