圆的周长可以定义为圆的外边界。它是圆的周长。圆周围的每个点都遵循某些属性，如下所示 -
-
点 (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
输入
S = “RURDLR”
R = 2
登录后复制
输出
Yes
登录后复制
说明
选择子序列“RR” -
最初，(0, 0) + R -> (1, 0) + R -> (2, 0)。
周长可能为 22 + 02 = 4 = R2
示例 2
输入
S = “UUUUU”
R = 6
登录后复制
输出
No
登录后复制
说明
选择最大的子序列“UUUU” -
最初，(0, 0) + U -> (0, 1) + U -> (0, 2) + U -> (0, 3) + U -> (0, 4) + U -> (0, 5)。
不可能达到圆周，因为 02 + 52 = 25 R2
方法 1：暴力破解
问题的解决方法是找到字符串S的所有可能的子序列，然后检查每个子序列是否可以到达圆周。通过维护 x 和 y 的计数器来检查这些条件，其中 x 在每个 L 上递减并在每个 R 上递增。类似地，y 在每个 D 上递减并在每个 U 上递增。然后检查 x2 + y2 = R2 检查终点是否在圆周上。
伪代码
procedure subsequence (S, sub, vec):
if S is empty
add sub to vec
return
end if
subsequence(S.substring(1), sub + S[0], vec)
subsequence(S.substring(1), sub, vec)
end procedure
procedure checkSeq (S, R)
x = 0
y = 0
for move in S do
if move == 'L' then
x = x - 1
else if move == 'R' then
x = x + 1
else if move == 'U' then
y = y + 1
else if move == 'D' then
y = y - 1
end if
if x^2 + y^2 = R^2 then
return true
end if
end for
return false
end procedure
procedure reachCircumference (S, R):
v = []
subsequence(S, "", v)
for str in v:
if checkSeq(str, R)
return "yes"
end if
return "no"
end procedure
登录后复制
示例：C++ 实现
在下面的程序中，创建字符串 S 的所有可能的子序列，并检查它们是否到达圆的圆周。
#include
using namespace std;
// Function to create all the possible subsequence of string S
void subsequence(string S, string sub, vector &vec){
// Base Case
if (S.empty()) {
vec.push_back(sub);
return;
}
// Subsequence including the character
subsequence(S.substr(1), sub + S[0], vec);
// Subsequence excluding the character
subsequence(S.substr(1), sub, vec);
}
// Function to check if a given sequence of steps lead to the circumference of the circle with radius R
bool checkSeq(string S, int R){
// Initialising centre of circle as (0, 0)
int x = 0, y = 0;
for (char move : S) {
if (move == 'L') {
x -= 1;
} else if (move == 'R') {
x += 1;
} else if (move == 'U') {
y += 1;
} else if (move == 'D') {
y -= 1;
}
// Check to find if (x, y) lie on circumference using the circle equation
if (x*x + y*y == R*R) {
return true;
}
}
return false;
}
// function to check if any subsequence of string S leads to any point on the circumference of the circle
string reachCircumference(string S, int R){
vector v;
string sub = "";
// Storing all subsequence in vector v
subsequence(S, sub, v);
// Checking the condition for each subsequence
for (auto str: v) {
if(checkSeq(str, R)) {
return "yes";
break;
}
}
return "no";
}
// Driver Code
int main(){
string S = "RURDLR";
int R = 2;
cout = mp[sq - i * i] and maxUD >= i
return “yes”
end if
if maxLR >= i && maxUD >= mp[sq - i * i]
return “yes”
end if
end if
end for
return “no”
end procedure
登录后复制
下面是 C++ 实现，
在下面的程序中，我们使用映射来检查是否存在通向圆周长的子序列。
#include
using namespace std;
// Function to check if any subsequence of string S leads to any point on the circumference of the circle
string reachCircumference (string S, int R){
// Counting total occurrenceof each L, R, U, D
int cL = 0, cR = 0, cD = 0, cU = 0;
for (char move : S) {
if (move == 'L') {
cL++;
} else if (move == 'R') {
cR++;
} else if (move == 'U') {
cU++;
} else if (move == 'D') {
cD++;
}
}
// Checking for a path to circumference using only one type of move
if (max(max(cL, cR), max(cD, cU)) >= R) {
return "yes";
}
int maxLR = max(cL, cR), maxUD = max(cU, cD);
unordered_map mp;
int sq = R * R;
for (int i = 1; i * i = mp[sq - i * i] && maxUD >= i)
return "yes";
// Checking if it is possible to reach (±i, ±mp[r_square-i*i])
if (maxLR >= i && maxUD >= mp[sq - i * i])
return "yes";
}
}
return "no";
}
// Driver Code
int main(){
string S = "RURDLR";
int R = 5;
cout
