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)에서 시작합니다.
- 북쪽으로 4단위를 (0, 4)로 이동하세요.
- 우회전.
- 동쪽으로 3단위를 (3, 4)로 이동하세요.
- 로봇이 원점에서 가장 먼 지점은 (3, 4)이며, 이 값의 제곱은 32 + 42 = 25단위입니다.
예 2:
-
입력: 명령 = [4,-1,4,-2,4], 장애물 = [[2,4]]
-
출력: 65
-
설명: 로봇은 (0, 0)에서 시작합니다.
- 북쪽으로 4단위를 (0, 4)로 이동하세요.
- 우회전.
- 동쪽으로 1칸 이동 후 (2, 4)의 장애물에 막히면 로봇은 (1, 4)에 있습니다.
- 좌회전하세요.
- 북쪽으로 4칸을 (1, 8)로 이동하세요.
- 로봇이 원점에서 가장 먼 지점은 (1, 8)이며, 이 값의 제곱은 12 + 82 = 65단위입니다.
예 3:
-
입력: 명령 = [6,-1,-1,6], 장애물 = []
-
출력: 36
- 설명: 로봇은 (0, 0)에서 시작합니다.
- 북쪽으로 6단위를 (0, 6)으로 이동하세요.
- 우회전.
- 우회전.
- 남쪽으로 6단위 이동하여 (0, 0)으로 이동합니다.
- 로봇이 원점에서 가장 먼 지점은 (0, 6)이며, 이 값의 제곱은 62 = 36 단위 떨어져 있습니다.
제약조건:
- 1 <= Commands.length <= 104
-
명령[i]은 -2, -1 또는 [1, 9] 범위의 정수입니다.
- 0 <= 장애물.길이 <= 104
- -3 * 104 <= xi, yi <= 3 * 104
- 답은 2 미만이 보장됩니다31
해결책:
우리는 일련의 명령을 기반으로 무한한 2D 그리드에서 로봇의 움직임을 시뮬레이션하고 장애물이 있는 경우 피해야 합니다. 목표는 로봇이 원점에서 도달하는 최대 유클리드 거리의 제곱을 구하는 것입니다.
접근하다
-
방향 처리:
- 로봇은 동서남북 4방향 중 하나를 향할 수 있습니다.
- 이러한 방향을 벡터로 나타낼 수 있습니다.
- 북쪽: (0, 1)
- 동쪽: (1, 0)
- 남쪽: (0, -1)
- 서쪽: (-1, 0)
-
회전:
- 좌회전(-2)하면 방향이 시계 반대 방향으로 90도 이동합니다.
- 우회전(-1)하면 방향이 시계 방향으로 90도 이동합니다.
-
이동:
- 각 이동 명령에 대해 로봇은 한 번에 한 유닛씩 현재 방향으로 이동합니다. 장애물을 만나면 해당 명령에 따라 이동을 멈춥니다.
-
장애물 추적:
- 빠른 조회를 위해 장애물 목록을 튜플 세트로 변환하면 로봇이 장애물에 부딪힐지 빠르게 판단할 수 있습니다.
-
거리 계산:
- 로봇이 이동 중 도달하는 원점에서 최대 거리의 제곱을 추적합니다.
이 솔루션을 PHP로 구현해 보겠습니다: 874. 걷는 로봇 시뮬레이션
설명:
-
방향 관리: 벡터 목록을 사용하여 방향을 나타내므로 이동 후 다음 위치를 쉽게 계산할 수 있습니다.
-
장애물 감지: 장애물을 세트로 저장하여 위치가 장애물에 의해 차단되었는지 확인하는 데 O(1) 시간 복잡도를 달성합니다.
-
거리 계산: 로봇이 이동하면서 도달하는 최대 제곱 거리를 지속적으로 업데이트합니다.
테스트 케이스
- 제공된 예제 테스트 사례는 솔루션을 검증하는 데 사용됩니다.
-
장애물이 없는 [4,-1,3]은 25를 반환해야 합니다.
-
장애물 [[2,4]]가 있는 [4,-1,4,-2,4]는 65를 반환해야 합니다.
-
장애물이 없는 [6,-1,-1,6]은 36을 반환해야 합니다.
이 솔루션은 문제 제약 조건을 효율적으로 처리하고 필요에 따라 최대 거리의 제곱을 계산합니다.
연락처 링크
이 시리즈가 도움이 되었다면 GitHub에서 저장소에 별표를 표시하거나 즐겨찾는 소셜 네트워크에서 게시물을 공유해 보세요. 여러분의 지원은 저에게 큰 의미가 될 것입니다!
이런 유용한 콘텐츠를 더 원하시면 저를 팔로우해주세요.
위 내용은 . 걷는 로봇 시뮬레이션의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!