Requête pour mettre à jour le nombre de cellules connectées non vides dans une matrice

Une matrice peut être considérée comme un ensemble de cellules organisées en lignes et en colonnes. Chaque cellule peut contenir une valeur, qui peut être vide ou non vide. En programmation informatique, les matrices sont souvent utilisées pour représenter les données dans une grille bidimensionnelle.

Dans cet article, nous verrons comment compter efficacement le nombre de cellules connectées non vides dans une matrice, en tenant compte des éventuelles mises à jour de la matrice. Nous explorerons différentes façons de résoudre ce problème et fournirons des exemples de code concrets pour démontrer la mise en œuvre.

Grammaire

La syntaxe de base pour interroger le nombre de cellules non vides connectées dans une matrice et la mettre à jour en utilisant C/C++ peut être définie comme suit -

int queryCount(int matrix[][MAX_COLS], int rows, int cols);

Où matrice est l'entrée "matrice", "lignes" et "cols" représentent respectivement le nombre de lignes et de colonnes dans la matrice. La fonction "queryCount" renvoie une valeur entière représentant le nombre de cellules connectées non vides dans la matrice.

Algorithme

Pour résoudre ce problème, nous pouvons suivre l'algorithme suivant -

Étape 1 - Initialisez la variable "count" à 0, cela stockera le nombre de cellules non vides connectées.

Étape 2 - Parcourez chaque cellule de la matrice.

Étape 3 - Pour chaque cellule, vérifiez si elle n'est pas vide (c'est-à-dire si elle contient une valeur non nulle).

Étape 4 - Si la cellule n'est pas vide, augmentez le nombre de 1.

Étape 5 - Vérifiez si la cellule a des cellules adjacentes non vides.

Étape 6 - Si la cellule adjacente n'est pas vide, augmentez le "compte" de 1.

Étape 7 - Répétez les étapes 5 à 6 pour toutes les cellules adjacentes.

Étape 8 - 8 : Après avoir parcouru toutes les cellules de la matrice, renvoyez le « compte » comme résultat final.

Méthode

• Méthode 1 - Une façon courante de résoudre ce problème consiste à utiliser l'algorithme Depth First Search (DFS)

• Méthode 2 - Une autre façon d'implémenter une requête pour trouver le nombre de cellules non vides avec des jointures dans une matrice mise à jour consiste à utiliser l'algorithme de recherche en largeur (BFS).

Méthode 1

Dans cette approche, l'algorithme DFS implique de parcourir de manière récursive la matrice et de garder une trace des cellules visitées pour éviter une double comptabilisation.

Exemple 1

Cette méthode effectue une recherche en profondeur d'abord sur une matrice bidimensionnelle. Les dimensions, les valeurs des cellules et le nombre de requêtes de la matrice sont déterminés de manière aléatoire. Le sous-programme countConnectedCells exécute DFS et renvoie un nombre de cellules connectées et non nulles, en commençant par la cellule de la ligne et de la colonne spécifiées. La fonction updateCell met à jour la valeur d'une cellule dans une matrice. La fonction principale démarre une graine aléatoire en utilisant l'heure actuelle, puis génère une taille et des éléments de matrice aléatoires, suivis d'un nombre aléatoire de requêtes. Pour chaque requête, le code sélectionne de manière aléatoire une requête de comptage (1) ou une requête de mise à jour (2) et exécute l'action appropriée. Si le type de la requête est 1, la fonction countConnectedCells est appelée pour déterminer le nombre de cellules connectées et non vides et imprime le résultat. Si le type de requête est 2, appelez la fonction updateCell pour ajuster la valeur de la cellule spécifiée.

#include <iostream>
using namespace std;

const int MAX_SIZE = 100; // Maximum size of the matrix

// Function to count connected non-empty cells using DFS
int countConnectedCells(int matrix[][MAX_SIZE], int rows, int cols, int row, int col, int visited[][MAX_SIZE]) {
   if (row < 0 || row >= rows || col < 0 || col >= cols || matrix[row][col] == 0 || visited[row][col])
      return 0;

   visited[row][col] = 1;
   int count = 1; // Counting the current cell as non-empty
   count += countConnectedCells(matrix, rows, cols, row - 1, col, visited); // Check top cell
   count += countConnectedCells(matrix, rows, cols, row + 1, col, visited); // Check bottom cell
   count += countConnectedCells(matrix, rows, cols, row, col - 1, visited); // Check left cell
   count += countConnectedCells(matrix, rows, cols, row, col + 1, visited); // Check right cell

   return count;
}

// Function to update a cell in the matrix
void updateCell(int matrix[][MAX_SIZE], int rows, int cols, int row, int col, int newValue) {
   matrix[row][col] = newValue;
}

// Function to initialize the matrix
void initializeMatrix(int matrix[][MAX_SIZE], int rows, int cols) {
   for (int i = 0; i <rows; i++) {
      for (int j = 0; j < cols; j++) {
         cin >> matrix[i][j]; // Taking input for each cell in the matrix
      }
   }
}

int main() {
   int rows, cols; // Input matrix size
   cin >> rows >> cols; // Taking input for matrix size

   int matrix[MAX_SIZE][MAX_SIZE]; // Matrix to store the values
   int visited[MAX_SIZE][MAX_SIZE] = {0}; // Visited matrix to keep track of visited cells

   initializeMatrix(matrix, rows, cols); // Initialize the matrix with input values

   int queries; // Input number of queries
   cin >> queries; // Taking input for number of queries

   for (int i = 0; i < queries; i++) {
      int queryType; // Input query type (1 for count query, 2 for update query)
      cin >> queryType; // Taking input for query type

      if (queryType == 1) {
         int row, col; // Input row and column for count query
         cin >> row >> col; // Taking input for row and column
         int count = countConnectedCells(matrix, rows, cols, row, col, visited); // Call countConnectedCells function
         cout << "Count of connected non-empty cells at (" << row << ", " << col << "): " << count << endl; // Print result
      } else if (queryType == 2) {
         int row, col, newValue; // Input row, column, and new value for update query
         cin >> row >> col >> newValue; // Taking input for row, column, and new value
         updateCell(matrix, rows, cols, row, col, newValue); // Call updateCell function
      }
   }
   return 0;
}

Sortie

Count of connected non-empty cells at (1, 2): 0
Count of connected non-empty cells at (0, 1): 2

Méthode 2

Dans cette approche, Breadth First Search (BFS) est un autre algorithme de parcours graphique qui peut être utilisé pour trouver le nombre de cellules non vides connectées dans une matrice. Dans BFS, nous partons d'une cellule donnée et explorons toutes ses cellules voisines en largeur (c'est-à-dire couche par couche). Nous utilisons une file d'attente pour garder une trace des cellules auxquelles nous accédons et marquons les cellules qui ont été consultées pour éviter plusieurs décomptes.

Exemple 2

Ce code constitue un logiciel qui effectue un algorithme de recherche en largeur sur une matrice bidimensionnelle. Les dimensions de la matrice, les valeurs des cellules et le nombre de requêtes sont générés arbitrairement. Le code contient deux sous-programmes : un pour exécuter BFS et un autre pour ajuster les cellules de la matrice.

Le fonctionnement BFS commence avec une cellule sélectionnée au hasard et vérifie ses cellules voisines pour déterminer si elles sont interconnectées et inoccupées. Si tel est le cas, ils seront ajoutés à la file d’attente et traités de la même manière. La mise à jour d'une cellule dans une matrice implique uniquement de modifier sa valeur. Après avoir généré la matrice et le numéro de requête, le code sélectionne de manière aléatoire une requête BFS ou une requête de mise à jour et effectue l'opération appropriée. Le résultat de la requête BFS est un décompte de cellules inoccupées interconnectées à partir de la cellule sélectionnée.

Code

#include <iostream>
#include <queue>
#include <ctime>
#include <cstdlib>

using namespace std;

const int MAX_SIZE = 100;

// Function to perform Breadth-First Search (BFS)
int bfs(int matrix[][MAX_SIZE], int rows, int cols, int row, int col, int visited[][MAX_SIZE]) {
   int count = 0;
   queue<pair<int, int>> q;
   q.push({row, col});

   while (!q.empty()) {
      pair<int, int> currentCell = q.front();
      q.pop();

      int currentRow = currentCell.first;
      int currentCol = currentCell.second;

      if (currentRow >= 0 && currentRow <rows && currentCol >= 0 && currentCol < cols && !visited[currentRow][currentCol] && matrix[currentRow][currentCol] == 1) {
         count++;
         visited[currentRow][currentCol] = 1;

         q.push({currentRow - 1, currentCol});
         q.push({currentRow + 1, currentCol});
         q.push({currentRow, currentCol - 1});
         q.push({currentRow, currentCol + 1});
      }
   }
   return count;
}
// Function to update a cell in the matrix
void updateCell(int matrix[][MAX_SIZE], int row, int col, int newValue) {
   matrix[row][col] = newValue;
}

// Function to generate a random integer between min and max (inclusive)
int randomInt(int min, int max) {
   return rand() % (max - min + 1) + min;
}

int main() {
   srand(time(0));

   int rows = randomInt(1, 10);
   int cols = randomInt(1, 10);

   int matrix[MAX_SIZE][MAX_SIZE];
   int visited[MAX_SIZE][MAX_SIZE] = {0};

   for (int i = 0; i < rows; i++) {
      for (int j = 0; j < cols; j++) {
         matrix[i][j] = randomInt(0, 1);
      }
   }

   int queries = randomInt(1, 5);

   for (int i = 0; i < queries; i++) {
      int queryType = randomInt(1, 2);

      if (queryType == 1) {
         int row = randomInt(0, rows - 1);
         int col = randomInt(0, cols - 1);
         int count = bfs(matrix, rows, cols, row, col, visited);
         cout << "Count of connected non-empty cells at (" << row << ", " << col << "): " << count << endl;
      } else if (queryType == 2) {
         int row = randomInt(0, rows - 1);
         int col = randomInt(0, cols - 1);
         int newValue = randomInt(0, 1);
         updateCell(matrix, row, col, newValue);
      }
   }
   return 0;
}

Sortie

Count of connected non-empty cells at (0, 0): 0

Conclusion

Dans cet article, nous avons discuté de deux méthodes pour trouver le nombre de cellules non vides connectées dans une matrice et les mettre à jour en utilisant C/C++. Algorithme Depth First Search (DFS) et recherche par union (union d’ensembles disjoints). Il est important d’analyser la complexité temporelle et spatiale de chaque méthode avant de choisir la méthode la plus appropriée pour un cas d’utilisation spécifique.

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!