Vérifie s'il est possible d'atteindre n'importe quel point de la circonférence d'un cercle donné depuis l'origine

La circonférence d'un cercle peut être définie comme la limite extérieure du cercle. C'est la circonférence du cercle. Chaque point autour du cercle suit certaines propriétés comme indiqué ci-dessous -

• Le point (x,y) se trouve à l'intérieur du cercle tel que $mathrm{x^2 + y^2

• Le point (x,y) se trouve sur le cercle tel que $mathrm{x^2 + y^2 = R^2}$

• Le point (x,y) est à l'extérieur du cercle tel que $mathrm{x^2 + y^2 > R^2}$

Où R = rayon du cercle.

Énoncé du problème

Étant donné une chaîne S représentant une séquence de mouvements (L, R, U, D) et un entier R représentant le rayon d'un cercle. Vérifiez si un point sur la circonférence d'un cercle de rayon R avec l'origine peut être atteint en sélectionnant n'importe quelle sous-séquence de mouvements à partir de S. Le fonctionnement de chaque mouvement est le suivant,

• L = réduire la coordonnée x

• R = coordonnée x incrémentale

• U = incrément de coordonnée y

• D = Diminution et coordonnée

Exemple 1

Entrez

S = “RURDLR”
R = 2

Sortie

yes

Instructions

Sélectionnez la sous-séquence "RR" -

Initialement, (0, 0) + R -> (1, 0) + R -> (2, 0).

Le périmètre peut être 2² + 02 = 4 = R²

Exemple 2

Entrez

S = “UUUUU”
R = 6

Sortie

no

Instructions

Sélectionnez la plus grande sous-séquence "UUUU" -

Initialement, (0, 0) + U -> (0, 1) + U -> (0, 2) + U -> (0, 3) + U -> (0, 4) + U -> (0 , 5).

Il est impossible d'atteindre la circonférence car 0² + 5² = 25 R²

Méthode 1 : Fissuration par force brute

La solution au problème est de trouver toutes les sous-séquences possibles de la chaîne S puis de vérifier si chaque sous-séquence peut atteindre le cercle. Ces conditions sont vérifiées en maintenant des compteurs pour x et y, où x est décrémenté sur chaque L et incrémenté sur chaque R. De même, y diminue à chaque D et augmente à chaque U. Vérifiez ensuite x² + y² = R² pour vérifier si le point final est sur la circonférence.

pseudocode

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

Exemple : implémentation C++

Dans le programme suivant, créez toutes les sous-séquences possibles de la chaîne S et vérifiez si elles atteignent la circonférence du cercle.

#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;
}

Sortie

yes

Méthode 2 : Méthode d'optimisation

Un moyen efficace de résoudre ce problème est de vérifier si la somme des carrés de x et y est égale au carré du rayon pour toute paire de x et y en utilisant (L, R, U ou D).

Tout d'abord, nous comptons le nombre maximum d'occurrences de chaque étape et vérifions si l'une d'entre elles est égale à R. S'il n'est pas égal, nous vérifions si un nombre quelconque de paires de L ou R et U ou D peuvent donner lieu à une origine de distance égale à R .

pseudocode

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

Ce qui suit est l'implémentation C++,

Dans le programme ci-dessous, nous utilisons une carte pour vérifier s'il existe une sous-séquence menant à la circonférence d'un cercle.

#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;
}

Sortie

no

Conclusion

En résumé, pour savoir si vous pouvez utiliser une sous-séquence d'étapes dans la chaîne S pour obtenir la circonférence d'un cercle centré à l'origine, vous pouvez utiliser l'une des méthodes ci-dessus. La deuxième méthode est une méthode plus rapide mais utilise de l'espace supplémentaire, tandis que la première méthode est une méthode par force brute qui n'est pas très efficace mais facile à comprendre.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!