Vérifie s'il y a T blocs consécutifs de 0 dans la matrice binaire donnée

Présentation

Les matrices binaires sont largement utilisées en informatique et dans divers domaines pour représenter efficacement des données ou résoudre des problèmes complexes. Dans certains cas, il devient important de déterminer si une matrice binaire donnée contient des blocs de zéros consécutifs. Dans cet article, nous allons explorer une solution élégante utilisant du code C++ qui nous permet de détecter la présence de T blocs de zéros consécutifs dans une matrice binaire donnée. Cette approche est à la fois intuitive et efficace, ce qui la rend adaptée à une mise en œuvre pratique.

Vérifiez s'il y a T blocs 0 consécutifs

Étant donné une matrice binaire bidimensionnelle de dimension N x M et un entier T, nous devons déterminer s'il y a T blocs de zéros consécutifs dans la matrice (où « contigu » signifie adjacent horizontalement ou verticalement). Pour y parvenir, décomposons le processus étape par étape à l'aide de méthodes logiques et algorithmiques.

Vérification des entrées

Avant de se lancer dans l'exploration de modèles dans des matrices binaires, il est important de vérifier les dimensions appropriées et les caractéristiques pertinentes de l'entrée utilisateur. Nous devons nous assurer que T se situe dans une plage acceptable pour fournir des résultats réalisables tout en maintenant l'efficacité du calcul.

Traverser les lignes et les colonnes

Pour identifier efficacement les blocs de zéros consécutifs, nous devons analyser les lignes et les colonnes séparément. Par exemple, en commençant par la première ligne (la plus haute), nous allons parcourir tous les éléments par colonne jusqu'à la ligne N (la plus basse). Le déplacement simultané des colonnes permet de capturer naturellement les séquences horizontales et verticales sans manquer aucune combinaison potentielle.

Détecter les blocs consécutifs

L'identification des zéros consécutifs constitue la pierre angulaire de la détection des blocs de zéros consécutifs lorsque nous parcourons chaque colonne de chaque ligne.

Une matrice binaire est un tableau composé uniquement de 0 et de 1, où chaque élément représente respectivement un état "off" ou "on". En analysant ces deux états, nous pouvons identifier des modèles uniques pouvant fournir des corrélations ou des arrangements uniques entre des éléments adjacents.

Exemple

La matrice binaire est considérée comme,

1 0 0 0 1
1 0 0 0 1
1 1 1 1 1
1 0 0 0 1

Nous devons trouver le nombre de blocs zéro consécutifs dans la matrice. La valeur de T est 3.

Nous pouvons utiliser Depth First Search (DFS) pour trouver des blocs consécutifs de zéros dans une matrice. Nous parcourons d’abord la matrice par lignes et colonnes. Si nous rencontrons un élément zéro auquel nous n'avons pas accédé auparavant, nous le plaçons sur la pile et démarrons DFS à partir de cet élément.

Pendant le processus DFS, nous vérifions les quatre cellules voisines (haut, bas, gauche, droite) de la cellule actuelle. Si l'une de ces cellules est nulle et n'a pas été consultée auparavant, nous la plaçons sur la pile et continuons DFS à partir de cette cellule.

Nous gardons également une trace du nombre de blocs zéro consécutifs rencontrés jusqu'à présent. Si ce décompte est supérieur ou égal à T, on renvoie "oui". Sinon, on continue DFS jusqu'à ce que toutes les cellules aient été visitées

Dans ce cas, nous effectuons une recherche en profondeur d'abord (DFS) à partir de la cellule (0,1). Nous rencontrons deux autres éléments nuls en (0,2) et (0,3) et les ajoutons à notre chemin actuel. Nous revenons ensuite à la cellule (0,1) et vérifions ses cellules voisines. Nous rencontrons un autre élément nul en (1,1) et l'ajoutons à notre chemin actuel. Ensuite, nous revenons à la cellule (0,1) et vérifions ses cellules voisines. Nous n'avons rencontré aucun élément zéro qui n'ait pas encore été visité

Ensuite, nous démarrons DFS à partir de la cellule (3,1). Nous rencontrons deux autres éléments nuls en (3,2) et (3,3) et les ajoutons à notre chemin actuel. Nous revenons ensuite à la cellule (3,1) et vérifions ses cellules voisines. Nous ne rencontrerons jamais un élément zéro que nous n’avons jamais visité auparavant.

Nous trouvons maintenant trois blocs de zéros consécutifs dans la matrice. Puisque ce compte est supérieur ou égal à T=3, la sortie est « Oui »

Méthode 1 : le code C++ vérifie s'il y a T blocs 0 consécutifs

Pour atteindre notre objectif, nous pouvons utiliser des techniques de parcours graphique sur une matrice binaire tout en gardant une trace des cellules visitées. Nous utiliserons l’algorithme Depth First Search (DFS) combiné au principe de backtracking.

Algorithme

Étape 1 : Initialisez les variables nécessaires, telles que la définition des constantes `N` et `M` pour représenter la taille de la matrice binaire d'entrée et la déclaration des tableaux booléens auxiliaires 'visité' et 'inCurrentPath', avec la taille de chaque tableau étant N x M, et définissez initialement tous les éléments des deux tableaux sur false

Étape 2 : Implémentez la fonction DFS et incluez la fonction principale

Étape 3 : Sur la base de la matrice binaire d'entrée, la sortie est imprimée comme oui ou non.

Exemple

#include<iostream>
#include<stack>
#include<bitset>

#define N 100
#define M 100

struct Node {
   int i;
   int j;
};

bool DFS(bool matrix[], int rows, int cols, int T)
{
   if(matrix == nullptr || rows <= 0 || cols <= 0 || T <= 0) // check for invalid input
      return false;

   std::bitset<N*M> visited; // declare bitset to mark visited cells
   std::bitset<N*M> inCurrentPath; // declare bitset to mark cells in current path
   std::stack<Node> s; // declare stack to store nodes for DFS

   for(int i=0;i<rows;++i){
      for(int j=0;j<cols;++j){

         if(matrix[i*cols+j] == 0 && !visited[i*cols+j]){

            s.push({i,j});
            int count = 0; // initialize count to zero for each new search

            while(!s.empty()){

               Node node = s.top();
               s.pop();

               if(node.i < 0 || node.i >= rows || node.j < 0 || node.j >= cols || visited[node.i*cols+node.j])
                  continue;

               visited[node.i*cols+node.j] = true;

               if(matrix[node.i*cols+node.j] == 0 && !inCurrentPath[node.i*cols+node.j]){
                  inCurrentPath[node.i*cols+node.j] = true;
                  count++;
               }

               if(count >= T){
                  std::cout << "Yes, the path is: "; // print yes and the path
                  for(int k=0;k<N*M;++k){
                     if(inCurrentPath[k]){
                        std::cout << "(" << k/cols << "," << k%cols << ") "; // print the coordinates of the cells in the path
                     }
                  }
                  std::cout << "\n";
                  return true;
               }

               s.push({node.i+1,node.j});
               s.push({node.i-1,node.j});
               s.push({node.i,node.j+1});
               s.push({node.i,node.j-1});
            }

            inCurrentPath.reset(); // reset the path after each search
         }
      }
   }

   std::cout << "No\n"; // print no if no path is found
   return false;
}

int main()
{
   bool matrix[N*M] = {1,1,0,0,1,
                  1,0,0,0,1,
                  1,1,1,1,1,
                  1,1,0,0,1,
                  }; // Binary matrix

   int T = 3; // Number of continuous blocks to find

   DFS(matrix, N, M, T); // call DFS function

   return 0;
}

Sortie

Yes, the path is: (0,2) (1,0) (1,1)

Conclusion

En tirant parti du code C++ proposé, qui utilise une technique de parcours graphique impliquant une recherche en profondeur d'abord (DFS), nous pouvons facilement déterminer si un nombre donné (T) de blocs de zéros consécutifs est présent dans une matrice binaire. Cette solution fournit un moyen efficace de résoudre les problèmes liés aux matrices binaires et permet aux chercheurs et développeurs de créer efficacement des algorithmes puissants.

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!