C++ 判断是否可能从原点到达给定圆的圆周上的任意点

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

• 点（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

解释

选择最长的子序列“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：优化方法

解决问题的一种高效方法是检查是否有任何x和y的组合（使用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;

// 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中的步骤子序列找到以原点为中心的圆的周长时，可以使用以上任何一种方法。第二种方法是一种更快的方法，但使用了额外的空间，而第一种方法是一种暴力方法，虽然不是很高效，但容易理解。