資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
