检查是否有可能从原点到达给定圆周上的任何点

圆的周长可以定义为圆的外边界。它是圆的周长。圆周围的每个点都遵循以下某些属性 -

• 点 (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 = 圆的半径。

问题陈述

给定一个表示移动序列 (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)。

可能达到周长，因为 2² + 02 = 4 = R²

示例 2

输入

S = "UUUUU"
R = 6

输出

NO

解释

选择最大子序列"UUUUU" −

最初，(0, 0) + U −> (0, 1) + U −> (0, 2) + U −> (0, 3) + U −> (0, 4) + U −> (0, 5)。

无法到达圆周，因为 0² + 5² = 25 R²

方法 1:强力

该问题的解决方案是找到字符串 S 的所有可能子序列，然后检查每个子序列是否可以到达圆周。通过维护 x 和 y 的计数器来检查这些条件，其中 x 在每个 L 上减少，在每个 R 上增加。类似地，y 在每个 D 上减少，在每个 U 上增加。然后检查 x² + y² = R² 是否检查最终点是否在圆周上。

伪代码

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;

// 创建字符串 S 的所有可能子序列的函数
void subsequence(string S, string sub, vector<string> &vec){

   // Base Case
   if (S.empty()) {
      vec.push_back(sub);
      return;
   }
   
    // 包含字符的子序列
    subsequence(S.substr(1), sub + S[0], vec);
    
    // 不包含字符的子序列
    subsequence(S.substr(1), sub, vec);
}

// 函数用于检查给定的步骤序列是否可得出半径为 R 的圆的周长
bool checkSeq(string S, int R){

   // 将圆心初始化为(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;
      }
      
      // 使用圆方程检查 (x, y) 是否位于圆周上
      if (x*x + y*y == R*R) {
         return true;
      }
   }
   return false;
}

// 函数检查字符串 S 的任何子序列是否指向圆周上的任意点
string reachCircumference(string S, int R){
    vector <string> v;
    string sub = "";
    
    // 将所有子序列存储在向量 v 中
    subsequence(S, sub, v);
    
    // 检查每个子序列的条件
   for (auto str: v) {
      if(checkSeq(str, R)) {
         return "yes";
         break;
      }
   }
   return "no";
}

// 驱动代码
int main(){
   string S = "RURDLR";
   int R = 2;
   cout << reachCircumference(S, R) << endl;
   return 0;
}

输出

yes

方法 2:优化方法

解决该问题的有效方法是检查使用 (L、R、U 或 D) 后，任何一对 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;

// 函数用于检查字符串 S 的任何子序列是否可到达圆周上的任何点
string reachCircumference (string S, int R){

   // 计算 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++;
      }
   }
   
   // 仅使用一种移动方式检查圆周路径
   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()) {
      
         // 检查是否有可能达到 (± mp[r_square - i*i], ± i)
         if (maxLR>= mp[sq - i * i] && maxUD >= i)
            return "yes";
            
         // 检查是否有可能达到 (±i, ±mp[r_square-i*i])
         if (maxLR >= i && maxUD >= mp[sq - i * i])
            return "yes";
      }
   }
   return "no";
}

// 驱动代码
int main(){
   string S = "RURDLR";
   int R = 5;
   cout << reachCircumference(S, R) << endl;
   return 0;
}

输出

no

结论

总之，要确定是否可以使用字符串 S 中的一系列步骤来求出以原点为中心的圆的周长，可以使用上述任何一种方法。第二种方法更快，但占用更多空间，而第一种方法(蛮力方法)效率不高，但易于理解。

相关文章

• 背面检测方法
• 检查字符串是否可以分成两个子序列，使得和的乘积为奇数
• 检查给定树的左视图是否已排序
• C++17 中的 std::string_view 类
• 检查是否可以通过将括号向两端移动最多 K 次来获得平衡括号
• 检查是否存在 2 * K + 1 个非空字符串，它们的连接构成给定的字符串
• 检查给定句子中子字符串 S1 是否出现在子字符串 S2 的任何出现之后
• 检查给定字符串的任何排列是否按字典顺序大于另一个给定字符串
• 在执行 K 个操作的所有可能选择后，给定二进制字符串中设置位数的平均值
• 通过执行交换操作检查两个字符串数组是否相等