원점에서 주어진 원의 둘레에 있는 임의의 지점에 도달할 수 있는지 확인합니다.

원의 원주는 원의 외부 경계로 정의할 수 있습니다. 원의 둘레입니다. 원 주위의 모든 점은 아래와 같이 특정 속성을 따릅니다. -

• 점 (x,y)는 $mathrm{x^2 + y^2

과 같이 원 안에 있습니다.

• 점(x,y)는 $mathrm{x^2 + y^2 = R^2}$

이 되는 원 위에 있습니다.

• 점(x,y)는 $mathrm{x^2 + y^2 > R^2}$

과 같이 원 외부에 있습니다.

여기서 R = 원의 반경.

문제 설명

일련의 이동(L, R, U, D)을 나타내는 문자열 S와 원의 반경을 나타내는 정수 R이 제공됩니다. S에서 시작하는 이동의 하위 시퀀스를 선택하여 원점과 반경 R인 원의 원주에 있는 지점에 도달할 수 있는지 확인합니다. 각 동작의 동작은 다음과 같습니다

• L = x 좌표 축소

• R = 증분 x 좌표

• U = y 좌표 증가

• D = y 좌표 감소

예 1

들어가세요

으아아아

출력

으아아아

지침

하위 시퀀스 "RR" 선택 -

처음에는 (0, 0) + R -> (1, 0) + R -> (2, 0)입니다.

주변은 2² + 02 = 4 = R²

일 수 있습니다.

예 2

들어가세요

으아아아

출력

으아아아

지침

가장 큰 부분 수열 "UUUU" 선택 -

처음에는 (0, 0) + U -> (0, 1) + U -> (0, 2) + U -> (0, 3) + U -> (0, 4) + U -> (0 , 5).

0² + 5² = 25R²

이므로 원주에 도달하는 것은 불가능합니다.

방법 1: 무차별 크래킹

문제의 해결책은 문자열 S의 가능한 모든 하위 수열을 찾은 다음 각 하위 수열이 원에 도달할 수 있는지 확인하는 것입니다. 이러한 조건은 x와 y에 대한 카운터를 유지함으로써 확인됩니다. 여기서 x는 각 L에서 감소하고 각 R에서 증가합니다. 마찬가지로 y는 D마다 감소하고 U마다 증가합니다. 그런 다음 x² + y² = R²를 확인하여 끝점이 원주에 있는지 확인하세요.

의사코드

으아아아

예: C++ 구현

다음 프로그램에서는 문자열 S의 가능한 모든 부분 수열을 만들고 그것이 원의 원주에 도달하는지 확인합니다.

으아아아

출력

으아아아

방법 2: 최적화 방법

이 문제를 해결하는 효율적인 방법은 (L, R, U 또는 D)를 사용하여 x와 y의 제곱의 합이 x와 y 쌍의 반지름의 제곱과 같은지 확인하는 것입니다.

먼저 각 단계의 최대 발생 횟수를 세어 그 중 R과 같은 것이 있는지 확인합니다. 같지 않으면 L 또는 R과 U 또는 D 쌍의 개수가 R과 동일한 거리 원점을 초래할 수 있는지 확인합니다.

의사코드

으아아아

다음은 C++ 구현입니다.

아래 프로그램에서는 지도를 사용하여 원주로 이어지는 부분 수열이 있는지 확인합니다.

으아아아

출력

으아아아

결론

요약하자면, 문자열 S에서 일련의 단계를 사용하여 원점을 중심으로 하는 원의 둘레를 구할 수 있는지 알아보려면 위의 방법 중 하나를 사용할 수 있습니다. 두 번째 방법은 더 빠른 방법이지만 추가 공간을 사용하는 반면, 첫 번째 방법은 그다지 효율적이지는 않지만 이해하기 쉬운 무차별 방법입니다.

위 내용은 원점에서 주어진 원의 둘레에 있는 임의의 지점에 도달할 수 있는지 확인합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!