Traduire les points de sortie dans une matrice binaire en utilisant C++

Une matrice binaire fait référence, en termes de programmation informatique, à une grille de lignes et de colonnes composées de 0 et de 1. L’un des défis de codage rencontrés lors des entretiens et des concours de programmation consiste à déterminer les points de sortie dans les matrices binaires. Dans cet article, nous expliquerons différentes manières de résoudre ce problème en utilisant C++.

Grammaire

Avant d'approfondir l'algorithme, nous trouverons peut-être utile de nous familiariser avec la syntaxe qui apparaît fréquemment dans les exemples de code que nous sommes sur le point de montrer.

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

Algorithme

Maintenant, décrivons l'algorithme étape par étape pour trouver le point de sortie dans une matrice binaire -

• Initialisez la position actuelle de la cellule à (0, 0).

• Parcourez la matrice à partir de la cellule actuelle.

• Si la cellule actuelle est 1, passez à la cellule suivante par ordre de priorité : droite, bas, gauche, haut.

• Si la cellule actuelle est 0, quittez la boucle et renvoyez la position actuelle de la cellule comme point de sortie.

• Répétez les étapes 3 et 4 jusqu'à ce que le point de sortie soit trouvé ou que toutes les cellules aient été visitées.

Méthode 1

La première méthode que nous recommandons consiste à implémenter une boucle while et des instructions conditionnelles pour exécuter l'algorithme. Voici un exemple montrant à quoi ressemblerait une telle implémentation -

Exemple

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

Sortie

Exit Point: (3, 3)

Méthode 2

Pour gérer le mouvement des cellules, notre deuxième méthode utilise une boucle do while combinée à une instruction switch. Pour référence, voici un exemple montrant à quoi ressemblerait une telle implémentation −

Exemple

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

Sortie

Exit Point: (3, 3)

La traduction chinoise de

Explication

est :

Explication

La fonction `findExitPoint` est conçue dans le code fourni. Son but est d'accepter une matrice binaire en entrée et de sortir une paire d'entiers correspondant aux coordonnées du point de sortie. Cette fonction suit l'algorithme décrit pour parcourir la matrice et trouver le point de sortie.

Pour garder une trace de la position actuelle de notre cellule lors du parcours de la matrice en utilisant les deux techniques d'implémentation, nous utilisons les variables « x » et « y ». Nous utilisons ensuite une boucle pour déplacer la matrice selon l'ordre de priorité : droite, bas, gauche et haut.

À l'aide d'une boucle while, nous vérifions la valeur de chaque cellule et utilisons des instructions if-else. En supposant que la cellule actuelle est 1, nous passons à la cellule suivante dans la direction spécifiée. Si la cellule actuelle est 0, nous sortons de la boucle et renvoyons la position actuelle de la cellule comme point de sortie.

La méthode 2 utilise une boucle do-while et une instruction switch pour gérer le mouvement des cellules. Pour rendre le processus de navigation efficace, nous utilisons un chemin d'exécution basé sur des conditions qui cible spécifiquement les mouvements dans la direction correspondant à chaque valeur de cellule actuelle donnée. Essentiellement, lorsque la cellule actuelle avec une valeur de 1 est traitée, elle est rapidement ajustée pour s'adapter à toutes les modifications nécessaires requises par nos valeurs de coordonnées x et y. En supposant que la cellule actuelle est 0, nous sortons de la boucle.

Dans la fonction `main`, nous initialisons une matrice binaire et appelons la fonction `findExitPoint` pour obtenir les coordonnées du point de sortie. Enfin, nous utilisons `cout` pour imprimer les coordonnées du point de sortie.

Conclusion

Une tâche de programmation fréquemment rencontrée consiste à trouver un point de sortie dans une matrice binaire, et cette tâche propose différentes voies de solution. Nous examinons en profondeur deux méthodes différentes, implémentées dans le code C++, pour surmonter cet obstacle dans cet article. L'application réussie de ces algorithmes peut déterminer efficacement la position finale d'une matrice binaire ou pointer vers une position finale. N'oubliez pas de choisir une stratégie qui correspond à vos préférences de style de codage et à vos objectifs finaux.

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!