Minimieren Sie die durch eine Zeichenfolge definierten Schritte, die erforderlich sind, um ein Ziel über einen bestimmten Quellpunkt zu erreichen

Die Minimierung der Anzahl der Schritte, die eine Zeichenfolge benötigt, um von einer bestimmten Quelle aus ein Ziel zu erreichen, ist ein häufiges Problem in der Informatik. Dabei geht es darum, anhand einer Reihe von Richtungen den kürzesten Weg von einem Startpunkt zu einem Zielpunkt zu finden. In diesem Artikel besprechen wir, wie dieses Problem in C++ gelöst werden kann, geben ein Beispiel und diskutieren Testfälle.

Problemstellung

Angesichts eines Startpunkts (x, y) und einer Richtungsfolge (N, S, E, W) auf einer 2D-Ebene müssen wir den kürzesten Weg vom Startpunkt zu einem Zielpunkt (x', y') finden. ). Jedes Zeichen in der Zeichenfolge stellt die Richtung dar, in die wir uns bewegen sollen. Wenn die Zeichenfolge beispielsweise „NNSE“ lautet, müssen wir uns zwei Schritte nach Norden, einen Schritt nach Süden und einen Schritt nach Osten bewegen. Wir können uns nur in die vier Himmelsrichtungen bewegen und nicht außerhalb der Ebene.

Methode

Um dieses Problem zu lösen, müssen wir eine Breitensuche (BFS) durch die zweidimensionale Ebene ausgehend vom Startpunkt durchführen. Während der Durchquerung müssen wir für jeden besuchten Punkt die Anzahl der Schritte berechnen, die erforderlich sind, um diesen Punkt zu erreichen. Wenn während der Durchquerung ein Zielpunkt angetroffen wird, geben wir die Anzahl der Schritte zurück, die erforderlich sind, um diesen Punkt zu erreichen.

Beispiel

Der folgende C++-Code implementiert die obige Methode.

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

Ausgabe

Destination cannot be reached

Der obige Code akzeptiert als Eingabe eine Zeichenfolge s, die die Richtung und den Startpunkt (x, y) darstellt. Wir initialisieren zunächst den aktuellen Punkt (curr_x, curr_y) auf (0, 0) und die Anzahl der Schritte zum Erreichen des aktuellen Punkts (Schritte) auf 0. Anschließend erstellen wir eine ungeordnete Karte, um die besuchten Punkte im Auge zu behalten. Wir durchlaufen die Zeichenfolge s und aktualisieren den aktuellen Punkt und die Anzahl der Schritte, die erforderlich sind, um diesen Punkt zu erreichen, basierend auf der durch das aktuelle Zeichen vorgegebenen Richtung. Wir prüfen, ob der aktuelle Punkt bereits besucht wurde. Wenn ja, überspringen Sie es. Andernfalls markieren wir es als besucht und erhöhen die Anzahl der Schritte, um den aktuellen Punkt zu erreichen.

Nachdem wir die Zeichenfolge durchlaufen haben, berechnen wir den Abstand zwischen dem Zielpunkt und dem aktuellen Punkt. Wenn die Entfernung zwischen dem Zielpunkt und dem aktuellen Punkt kleiner oder gleich der Anzahl der zurückgelegten Schritte ist und die Differenz zwischen der Anzahl der zurückgelegten Schritte und der Entfernung eine gerade Zahl ist, wird die Anzahl der zurückgelegten Schritte als zurückgegeben Mindestanzahl von Schritten, die erforderlich sind, um das Ziel zu erreichen. Andernfalls geben wir -1 zurück, was darauf hinweist, dass das Ziel nicht erreicht werden kann.

Testfallbeispiel

Betrachten wir einen Beispieltestfall, um zu verstehen, wie der obige Code funktioniert -

Eintreten

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

Im Beispieltestfall ist der Startpunkt (0,0) und die Richtung ist „NNSE“. Der Zielpunkt ist (2,2). Wenn wir jedoch der vorgegebenen Richtung folgen, erreichen wir nur den Punkt (0,2), nicht den Zielpunkt. Daher kann der Zielpunkt (2,2) in der angegebenen Richtung nicht erreicht werden.

Fazit

In diesem Artikel haben wir besprochen, wie man die Anzahl der Schritte minimiert, die erforderlich sind, um von einer bestimmten Quelle aus basierend auf einer Richtungsfolge ein Ziel zu erreichen. Wir haben die Lösung mithilfe von BFS-Traversal in C++ implementiert und ein Beispiel bereitgestellt, um die Funktionsweise des Codes zu veranschaulichen. Indem Sie die in diesem Artikel beschriebenen Methoden befolgen, können Sie ähnliche Probleme in C++ effektiv lösen.

Das obige ist der detaillierte Inhalt vonMinimieren Sie die durch eine Zeichenfolge definierten Schritte, die erforderlich sind, um ein Ziel über einen bestimmten Quellpunkt zu erreichen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!