Minimumkan langkah yang ditentukan rentetan yang diperlukan untuk mencapai destinasi melalui titik sumber tertentu

Meminimumkan bilangan langkah yang diperlukan oleh rentetan untuk mencapai destinasi daripada sumber tertentu adalah masalah biasa dalam sains komputer. Ia melibatkan mencari laluan terpendek dari titik permulaan ke titik destinasi berdasarkan set arah. Dalam artikel ini, kami akan membincangkan cara menyelesaikan masalah ini dalam C++, memberikan contoh dan membincangkan kes ujian.

Pernyataan Masalah

Memandangkan titik permulaan (x, y) dan urutan arah (N, S, E, W) pada satah 2D, kita perlu mencari laluan terpendek dari titik permulaan ke titik destinasi (x', y' ). Setiap aksara dalam rentetan mewakili arah yang patut kita gerakkan. Sebagai contoh, jika rentetan ialah "NNSE", maka kita perlu bergerak dua langkah ke utara, satu langkah ke selatan dan satu langkah ke timur. Kami hanya boleh bergerak dalam empat arah mata angin dan bukan di luar pesawat.

Kaedah

Untuk menyelesaikan masalah ini, kita perlu melakukan pencarian luas pertama (BFS) lintasan satah dua dimensi bermula dari titik permulaan. Semasa merentasi, untuk setiap titik yang dilawati, kita perlu mengira bilangan langkah yang diperlukan untuk mencapai titik tersebut. Jika titik sasaran ditemui semasa traversal, kami mengembalikan bilangan langkah yang diperlukan untuk mencapai titik itu.

Contoh

Kod C++ berikut melaksanakan kaedah di atas.

#include<bits/stdc++.h>
using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};

int minSteps(string s, int x, int y) {
   int n = s.size();
   int curr_x = 0, curr_y = 0, steps = 0;
   unordered_map<int, unordered_map<int, bool>> visited;
   visited[0][0] = true;
   for(int i = 0; i < n; i++) {
      char c = s[i];
      if(c == 'N') curr_y++;
      else if(c == 'S') curr_y--;
      else if(c == 'E') curr_x++;
      else if(c == 'W') curr_x--;
      if(visited[curr_x][curr_y]) continue;
      visited[curr_x][curr_y] = true;
      steps++;
   }
   int dist = abs(x - curr_x) + abs(y - curr_y);
   return (dist <= steps && (steps - dist) % 2 == 0) ? steps : -1;
}

int main() {
   string s = "NNSE";
   int x = 2, y = 2;
   int res = minSteps(s, x, y);
   if(res == -1) cout << "Destination cannot be reached\n";
   else cout << "Minimum steps to reach destination: " << res << "\n";
   return 0;
}

Output

Destination cannot be reached

Kod di atas menerima rentetan s yang mewakili arah dan titik permulaan (x, y) sebagai input. Kami mula-mula memulakan titik semasa (curr_x, curr_y) kepada (0, 0) dan bilangan langkah untuk mencapai titik semasa (langkah) kepada 0. Kami kemudian membuat peta yang tidak tersusun untuk menjejaki titik yang dilawati. Kami mengulangi rentetan s dan mengemas kini titik semasa dan bilangan langkah yang diperlukan untuk mencapai titik itu berdasarkan arah yang diberikan oleh aksara semasa. Kami menyemak sama ada titik semasa telah dilawati. Jika ya, langkau. Jika tidak, kami menandakannya sebagai dilawati dan menambah bilangan langkah untuk mencapai titik semasa.

Selepas melintasi rentetan, kami mengira jarak antara titik sasaran dan titik semasa. Jika jarak antara titik sasaran dan titik semasa adalah kurang daripada atau sama dengan bilangan langkah yang diambil, dan perbezaan antara bilangan langkah yang diambil dan jarak adalah nombor genap, maka bilangan langkah yang diambil dikembalikan sebagai bilangan langkah minimum yang diperlukan untuk sampai ke destinasi. Jika tidak, kami kembali -1, menunjukkan bahawa destinasi tidak dapat dicapai.

Contoh kes ujian

Mari kita pertimbangkan contoh kes ujian untuk memahami cara kod di atas berfungsi -

Masuk

string s = "NNSE";
int x = 2, y = 2;

Dalam contoh kes ujian, titik permulaan ialah (0,0) dan arahnya ialah "NNSE". Titik sasaran ialah (2,2). Namun, jika mengikut arahan yang diberikan, kita hanya akan sampai ke titik (0,2), bukan titik sasaran. Oleh itu, titik sasaran (2,2) tidak boleh dicapai dalam arah yang diberikan.

Kesimpulan

Dalam artikel ini, kami membincangkan cara meminimumkan bilangan langkah yang diperlukan untuk sampai ke destinasi daripada sumber tertentu berdasarkan urutan arah. Kami melaksanakan penyelesaian dalam C++ menggunakan traversal BFS dan memberikan contoh untuk menggambarkan cara kod tersebut berfungsi. Dengan mengikuti kaedah yang dibincangkan dalam artikel ini, anda boleh menyelesaikan masalah serupa dalam C++ dengan berkesan.

Atas ialah kandungan terperinci Minimumkan langkah yang ditentukan rentetan yang diperlukan untuk mencapai destinasi melalui titik sumber tertentu. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!