数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究检查是否可以从原点到达给定圆周上的任意一点
圆的周长可以定义为圆的外边界。它是圆的周长。圆周围的每个点都遵循以下属性：
位于圆内的点 (x,y)，使得 $\mathrm{x^2 + y^2 < R^2}$
位于圆上的点 (x,y)，使得 $\mathrm{x^2 + y^2 = R^2}$
位于圆外的点 (x,y)，使得 $\mathrm{x^2 + y^2 > R^2}$
其中 R = 圆的半径。
问题陈述
给定一个字符串 S，表示一系列移动 (L, R, U, D)，以及一个整数 R，表示圆的半径。检查是否可以通过从 S 中选择任何移动子序列来从原点到达半径为 R 的圆的任意一点。每个移动的操作如下所示：
L = x 坐标减 1
R = x 坐标加 1
U = y 坐标加 1
D = y 坐标减 1
示例 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
解释
选择最大的子序列“UUUUU” -
最初，(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 <bits/stdc++.h>
using namespace std;
// Function to create all the possible subsequence of string S
void subsequence(string S, string sub, vector<string> &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 <string> 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 << reachCircumference(S, R) << endl;
return 0;
}
输出
yes
方法 2：优化方法
解决该问题的一种有效方法是检查使用 (L、R、U 或 D) 后，任何一对 x 和 y 是否具有 x 和 y 的平方和等于半径的平方。
首先，我们计算每个步骤的最大出现次数，并检查是否任何一个等于 R。如果不是，那么我们检查 L 或 R 和 U 或 D 的任意数量的对是否可以导致到原点的距离等于 R。
伪代码
procedure reachCircumference (S, R)
cL = 0
cR = 0
cD = 0
cU = 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
if max(max(cL, cR), max(cD, cU)) >= R
return “yes”
maxLR = max(cL, cR)
maxUD = max(cU, cD)
Initialise unordered map mp
sq = R * R
for i = 1 till i * i = sq
if sq - i*i is not in the map
if maxLR>= 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++ 实现：
在下面的程序中，我们使用 map 来检查任何导致圆周的子序列。
#include <bits/stdc++.h>
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<int, int> mp;
int sq = R * R;
for (int i = 1; i * i <= sq; i++) {
mp[i * i] = i;
if (mp.find(sq - i * i) != mp.end()) {
// Checking if it is possible to reach (± mp[r_square - i*i], ± i)
if (maxLR>= 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 << reachCircumference(S, R) << endl;
return 0;
}
输出
no
结论
总之，要找到是否可以使用字符串 S 中步骤的子序列到达以原点为中心的圆的圆周，可以使用上述任何一种方法。第二种方法是一种更快的方法，但使用了额外的空间，而第一种方法（暴力法）效率不高，但易于理解。
52 次浏览
