檢查是否可能從原點到達給定圓的周長上的任意點

圓的周長可以定義為圓的外邊界。它是圓的周長。圓周圍的每個點都遵循某些屬性，如下所示 -

• 點 (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)。

週長可能為 2² 02 = 4 = R²

範例 2

輸入

S = “UUUUU”
R = 6

輸出

no

說明

選擇最大的子序列「UUUU」 -

最初，(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;

// 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 實現，

在下面的程式中，我們使用映射來檢查是否存在通往圓週長的子序列。

#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 中的步驟子序列來獲得以原點為中心的圓的周長，可以使用上述任何方法。第二種方法是更快的方法，但使用額外的空間，而第一種方法是強力方法，效率不是很高，但易於理解。

以上是檢查是否可能從原點到達給定圓的周長上的任意點的詳細內容。更多資訊請關注PHP中文網其他相關文章！