. 걷는 로봇 시뮬레이션

874. 걷는 로봇 시뮬레이션

난이도:중

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

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

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

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

로봇이 원점 제곱에서 얻은 최대 유클리드 거리를 반환합니다(즉, 거리가 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 <= 10⁴
• 명령[i]은 -2, -1 또는 [1, 9] 범위의 정수입니다.
• 0 <= 장애물.길이 <= 10⁴
• -3 * 10⁴ <= x_i, y_i <= 3 * 10⁴
• 답은 2 미만이 보장됩니다³¹

해결책:

우리는 일련의 명령을 기반으로 무한한 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!