Menyemak sama ada adalah mungkin untuk mencapai mana-mana titik pada lilitan bulatan tertentu dari asal

Lilitan bulatan boleh ditakrifkan sebagai sempadan luar bulatan. Ia adalah lilitan bulatan. Setiap titik di sekeliling bulatan mengikut sifat tertentu seperti yang ditunjukkan di bawah -

• Titik (x,y) terletak di dalam bulatan supaya $mathrm{x^2 + y^2

• Titik (x,y) terletak pada bulatan supaya $mathrm{x^2 + y^2 = R^2}$

• Titik (x,y) berada di luar bulatan sehingga $mathrm{x^2 + y^2 > R^2}$

Di mana R = jejari bulatan.

Pernyataan Masalah

Diberi rentetan S mewakili urutan pergerakan (L, R, U, D) dan integer R mewakili jejari bulatan. Periksa sama ada sebarang titik pada lilitan bulatan berjejari R dengan asalan boleh dicapai dengan memilih mana-mana urutan pergerakan bermula dari S. Operasi setiap pergerakan adalah seperti berikut,

• L = kurangkan x koordinat

• R = incremental x koordinat

• U = kenaikan koordinat y

• D = Menurunkan koordinat y

Contoh 1

Masuk

S = “RURDLR”
R = 2

Output

yes

Arahan

Pilih "RR" seterusnya -

Pada mulanya, (0, 0) + R -> (1, 0) + R -> (2, 0).

Perimeter mungkin 2² + 02 = 4 = R²

Contoh 2

Masuk

S = “UUUUU”
R = 6

Output

no

Arahan

Pilih urutan terbesar "UUUU" -

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

Mustahil untuk mencapai lilitan kerana 0² + 5² = 25 R²

Kaedah 1: Brute force cracking

Penyelesaian kepada masalah ini ialah mencari semua kemungkinan urutan rentetan S dan kemudian semak sama ada setiap urutan boleh mencapai bulatan. Keadaan ini disemak dengan mengekalkan pembilang untuk x dan y, di mana x dikurangkan pada setiap L dan dinaikkan pada setiap R. Begitu juga, y berkurangan pada setiap D dan meningkat pada setiap U. Kemudian tandakan x² + y² = R² untuk menyemak sama ada titik akhir berada pada lilitan.

pseudokod

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

Contoh: Pelaksanaan C++

Dalam program berikut, cipta semua kemungkinan urutan rentetan S dan semak sama ada ia mencapai lilitan bulatan.

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

Output

yes

Kaedah 2: Kaedah pengoptimuman

Cara yang cekap untuk menyelesaikan masalah ini ialah dengan memeriksa sama ada hasil tambah kuasa dua x dan y adalah sama dengan kuasa dua jejari untuk mana-mana pasangan x dan y menggunakan (L, R, U atau D).

Pertama, kami mengira bilangan maksimum kejadian setiap langkah dan menyemak sama ada mana-mana daripadanya sama dengan R. Jika tidak sama, maka kita semak sama ada sebarang bilangan pasangan L atau R dan U atau D boleh menghasilkan asalan jarak sama dengan R .

pseudokod

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

Berikut ialah pelaksanaan C++,

Dalam program di bawah, kami menggunakan peta untuk menyemak sama ada terdapat urutan yang membawa kepada lilitan bulatan.

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

Output

no

Kesimpulan

Ringkasnya, untuk mengetahui sama ada anda boleh menggunakan urutan langkah dalam rentetan S untuk mendapatkan lilitan bulatan berpusat pada asal, anda boleh menggunakan mana-mana kaedah di atas. Kaedah kedua adalah kaedah yang lebih pantas tetapi menggunakan ruang tambahan, manakala kaedah pertama adalah kaedah brute force yang tidak begitu cekap tetapi mudah difahami.

Atas ialah kandungan terperinci Menyemak sama ada adalah mungkin untuk mencapai mana-mana titik pada lilitan bulatan tertentu dari asal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!