Übersetzen Sie Ausstiegspunkte in einer Binärmatrix mit C++

Eine binäre Matrix bezieht sich in der Computerprogrammierung auf ein Raster aus Zeilen und Spalten, das aus Nullen und Einsen besteht. Eine Codierungsherausforderung bei der Programmierung von Interviews und Wettbewerben besteht darin, Ausstiegspunkte in binären Matrizen zu bestimmen. In diesem Artikel erklären wir verschiedene Möglichkeiten, dieses Problem mit C++ zu lösen.

Grammatik

Bevor wir uns mit dem Algorithmus befassen, kann es hilfreich sein, sich mit der Syntax vertraut zu machen, die in den Codebeispielen, die wir gleich zeigen, häufig vorkommt.

`pair<int, int> findExitPoint(const vector<vector<int>>& matrix)`.

Algorithmus

Lassen Sie uns nun den Schritt-für-Schritt-Algorithmus zum Finden des Austrittspunkts in einer binären Matrix skizzieren -

• Initialisieren Sie die aktuelle Zellenposition auf (0, 0).

• Durchlaufen Sie die Matrix ausgehend von der aktuellen Zelle.

• Wenn die aktuelle Zelle 1 ist, wechseln Sie in der Reihenfolge ihrer Priorität zur nächsten Zelle – rechts, unten, links, oben.

• Wenn die aktuelle Zelle 0 ist, verlassen Sie die Schleife und geben Sie die aktuelle Zellenposition als Ausgangspunkt zurück.

• Wiederholen Sie die Schritte 3 und 4, bis der Austrittspunkt gefunden ist oder alle Zellen besucht wurden.

Methode 1

Die erste Möglichkeit, die wir empfehlen, ist die Implementierung einer While-Schleife und bedingter Anweisungen zur Ausführung des Algorithmus. Hier ist ein Beispiel, das zeigt, wie eine solche Implementierung aussehen würde -

Beispiel

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findExitPoint(const vector<vector<int>>& matrix) {
   int rows = matrix.size();
   int cols = matrix[0].size();
   int x = 0, y = 0;  // Starting cell position

   while (x >= 0 && x < rows && y >= 0 && y < cols) {
      if (matrix[x][y] == 1) {
         // Move right
         if (y + 1 < cols && matrix[x][y + 1] == 1)
            y++;
         // Move down
         else if (x + 1 < rows && matrix[x + 1][y] == 1)
            x++;
         // Move left
         else if (y - 1 >= 0 && matrix[x][y - 1] == 1)
            y--;
         // Move up
         else if (x - 1 >= 0 && matrix[x - 1][y] == 1)
            x--;
      } else {
         break;  // Exit loop when encountering a 0
      }
   }

   return make_pair(x, y);
}

int main() {
   // Matrix initialization
   vector<vector<int>> matrix = {
      {1, 0, 0, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
   };

   // Finding the exit point
   pair<int, int> exitPoint = findExitPoint(matrix);

   // Printing the exit point coordinates
   cout << "Exit Point: (" << exitPoint.first << ", " << exitPoint.second << ")" << endl;

   return 0;
}

Ausgabe

Exit Point: (3, 3)

Methode 2

Um die Zellbewegung zu handhaben, verwendet unsere zweite Methode eine do while-Schleife kombiniert mit einer switch-Anweisung. Als Referenz finden Sie hier ein Beispiel, das zeigt, wie eine solche Implementierung aussehen würde −

Beispiel

#include <iostream>
#include <vector>
using namespace std;

pair<int, int> findExitPoint(const vector<vector<int>>& matrix) {
   int rows = matrix.size();
   int cols = matrix[0].size();
   int x = 0, y = 0;  // Starting cell position

   do {
      switch (matrix[x][y]) {
         case 1:  // Move based on the priority order
            if (y + 1 < cols && matrix[x][y + 1] == 1) {
               y++;  // Move right
            } else if (x + 1 < rows && matrix[x + 1][y] == 1) {
               x++;  // Move down
            } else if (y - 1 >= 0 && matrix[x][y - 1] == 1) {
               y--;  // Move left
            } else if (x - 1 >= 0 && matrix[x - 1][y] == 1) {
               x--;  // Move up
            }
            break;
   
            default:  // Exit loop when encountering a 0
         break;
      }
   } while (x >= 0 && x < rows && y >= 0 && y < cols);

   return make_pair(x, y);
}

int main() {
   // Matrix initialization
   vector<vector<int>> matrix = {
      {1, 0, 0, 1},
      {1, 1, 0, 1},
      {0, 1, 1, 1},
      {0, 0, 0, 1}
   };

   // Finding the exit point
   pair<int, int> exitPoint = findExitPoint(matrix);
   
   // Printing the exit point coordinates
   cout << "Exit Point: (" << exitPoint.first << ", " << exitPoint.second << ")" << endl;

   return 0;
}

Ausgabe

Exit Point: (3, 3)

Die chinesische Übersetzung von

Erklärung

lautet:

Erklärung

Die Funktion „findExitPoint“ ist im bereitgestellten Code entworfen. Sein Zweck besteht darin, eine binäre Matrix als Eingabe zu akzeptieren und ein Paar ganzer Zahlen auszugeben, die den Koordinaten des Austrittspunkts entsprechen. Diese Funktion folgt dem beschriebenen Algorithmus, um die Matrix zu durchqueren und den Austrittspunkt zu finden.

Um den Überblick über unsere aktuelle Zellposition zu behalten, wenn wir die Matrix mit beiden Implementierungstechniken durchlaufen, verwenden wir die Variablen „x“ und „y“. Anschließend verwenden wir eine Schleife, um die Matrix entsprechend der Rangfolge zu verschieben: rechts, unten, links und oben.

Mit einer While-Schleife überprüfen wir den Wert jeder Zelle und verwenden if-else-Anweisungen. Angenommen, die aktuelle Zelle ist 1, bewegen wir uns in der angegebenen Richtung zur nächsten Zelle. Wenn die aktuelle Zelle 0 ist, brechen wir aus der Schleife aus und geben die aktuelle Zellenposition als Ausgangspunkt zurück.

Methode 2 verwendet eine Do-While-Schleife und eine Switch-Anweisung, um die Zellbewegung zu verarbeiten. Um den Navigationsprozess effizient zu gestalten, verwenden wir einen bedingungsbasierten Ausführungspfad, der speziell auf Bewegungen in die Richtung abzielt, die jedem gegebenen aktuellen Zellenwert entspricht. Wenn die aktuelle Zelle mit dem Wert 1 verarbeitet wird, wird sie im Wesentlichen schnell angepasst, um alle erforderlichen Änderungen an unseren x- und y-Koordinatenwerten zu berücksichtigen. Unter der Annahme, dass die aktuelle Zelle 0 ist, brechen wir aus der Schleife aus.

In der Funktion „main“ initialisieren wir eine Binärmatrix und rufen die Funktion „findExitPoint“ auf, um die Koordinaten des Austrittspunkts zu erhalten. Schließlich verwenden wir „cout“, um die Koordinaten des Ausstiegspunkts auszugeben.

Fazit

Eine häufig auftretende Programmieraufgabe besteht darin, einen Austrittspunkt in einer Binärmatrix zu finden, und diese Aufgabe schlägt verschiedene Lösungswege vor. In diesem Artikel befassen wir uns eingehend mit zwei verschiedenen Methoden, die in C++-Code implementiert sind, um dieses Hindernis zu überwinden. Durch die erfolgreiche Anwendung dieser Algorithmen kann die Endposition einer binären Matrix effizient bestimmt oder auf eine Endposition verwiesen werden. Denken Sie daran, eine Strategie zu wählen, die Ihren gewünschten Programmierstilpräferenzen und Endzielen entspricht.

Das obige ist der detaillierte Inhalt vonÜbersetzen Sie Ausstiegspunkte in einer Binärmatrix mit C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!