Abfrage zum Aktualisieren der Anzahl verbundener nicht leerer Zellen in einer Matrix

Eine Matrix kann man sich als eine Sammlung von Zellen vorstellen, die in Zeilen und Spalten organisiert sind. Jede Zelle kann einen Wert enthalten, der leer oder nicht leer sein kann. In der Computerprogrammierung werden Matrizen häufig verwendet, um Daten in einem zweidimensionalen Raster darzustellen.

In diesem Artikel besprechen wir, wie man die Anzahl verbundener, nicht leerer Zellen in einer Matrix effizient zählt und dabei mögliche Aktualisierungen der Matrix berücksichtigt. Wir werden verschiedene Möglichkeiten zur Lösung dieses Problems untersuchen und reale Codebeispiele bereitstellen, um die Implementierung zu demonstrieren.

Grammatik

Die grundlegende Syntax zum Abfragen der Anzahl verbundener nicht leerer Zellen in einer Matrix und deren Aktualisierung mithilfe von C/C++ kann wie folgt definiert werden -

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

Wobei Matrix die Eingabe „Matrix“ ist, repräsentieren „Zeilen“ und „Spalten“ die Anzahl der Zeilen bzw. Spalten in der Matrix. Die Funktion „queryCount“ gibt einen ganzzahligen Wert zurück, der die Anzahl der verbundenen, nicht leeren Zellen in der Matrix darstellt.

Algorithmus

Um dieses Problem zu lösen, können wir dem folgenden Algorithmus folgen -

Schritt 1 – Initialisieren Sie die Variable „count“ auf 0, dadurch wird die Anzahl der verbundenen, nicht leeren Zellen gespeichert.

Schritt 2 – Iterieren Sie über jede Zelle in der Matrix.

Schritt 3 – Überprüfen Sie für jede Zelle, ob sie nicht leer ist (d. h. einen Wert ungleich Null enthält).

Schritt 4 – Wenn die Zelle nicht leer ist, erhöhen Sie die Anzahl um 1.

Schritt 5 – Überprüfen Sie, ob die Zelle nicht leere angrenzende Zellen hat.

Schritt 6 – Wenn die angrenzende Zelle nicht leer ist, erhöhen Sie die „Zählung“ um 1.

Schritt 7 – Wiederholen Sie die Schritte 5-6 für alle angrenzenden Zellen.

Schritt 8 - 8: Nachdem Sie alle Zellen in der Matrix durchlaufen haben, geben Sie die „Zählung“ als Endergebnis zurück.

Methode

• Methode 1 – Eine gängige Methode zur Lösung dieses Problems ist die Verwendung des DFS-Algorithmus (Depth First Search)

• Methode 2 – Eine weitere Möglichkeit, eine Abfrage zu implementieren, um die Anzahl nicht leerer Zellen mit Verknüpfungen in einer aktualisierten Matrix zu ermitteln, ist die Verwendung des BFS-Algorithmus (Breadth-First Search).

Methode 1

Bei diesem Ansatz beinhaltet der DFS-Algorithmus das rekursive Durchlaufen der Matrix und das Verfolgen der besuchten Zellen, um Doppelzählungen zu vermeiden.

Beispiel 1

Diese Methode führt eine Tiefensuche in einer zweidimensionalen Matrix durch. Die Dimensionen, Zellwerte und die Anzahl der Abfragen der Matrix werden zufällig bestimmt. Die Unterroutine „countConnectedCells“ führt DFS durch und gibt eine Anzahl verbundener, nicht leerer Zellen zurück, beginnend mit der Zelle in der angegebenen Zeile und Spalte. Die updateCell-Funktion aktualisiert den Wert einer Zelle in einer Matrix. Die Hauptfunktion startet einen zufälligen Startwert unter Verwendung der aktuellen Zeit, generiert dann eine zufällige Matrixgröße und Elemente, gefolgt von einer zufälligen Anzahl von Abfragen. Für jede Abfrage wählt der Code zufällig eine Zählabfrage (1) oder eine Aktualisierungsabfrage (2) aus und führt die entsprechende Aktion aus. Wenn der Abfragetyp 1 ist, wird die Funktion countConnectedCells aufgerufen, um die Anzahl der verbundenen, nicht leeren Zellen zu ermitteln und das Ergebnis auszugeben. Wenn der Abfragetyp 2 ist, rufen Sie die Funktion updateCell auf, um den Wert der angegebenen Zelle anzupassen.

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

Ausgabe

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

Methode 2

Bei diesem Ansatz ist Breadth First Search (BFS) ein weiterer Graph-Traversal-Algorithmus, der verwendet werden kann, um die Anzahl verbundener, nicht leerer Zellen in einer Matrix zu ermitteln. In BFS beginnen wir mit einer bestimmten Zelle und erkunden alle benachbarten Zellen in der Breitenrichtung (d. h. Schicht für Schicht). Wir verwenden eine Warteschlange, um zu verfolgen, auf welche Zellen zugegriffen wird, und markieren Zellen, auf die zugegriffen wurde, um Mehrfachzählungen zu vermeiden.

Beispiel 2

Dieser Code stellt eine Software dar, die einen Breitensuchalgorithmus für eine zweidimensionale Matrix ausführt. Die Dimensionen der Matrix, die Zellwerte und die Anzahl der Abfragen werden willkürlich generiert. Der Code enthält zwei Unterroutinen: eine zum Durchführen von BFS und eine andere zum Anpassen der Zellen innerhalb der Matrix.

Der BFS-Vorgang beginnt mit einer zufällig ausgewählten Zelle und überprüft die benachbarten Zellen, um festzustellen, ob sie miteinander verbunden und nicht belegt sind. Wenn dies der Fall ist, werden sie an die Warteschlange angehängt und auf ähnliche Weise verarbeitet. Das Aktualisieren einer Zelle innerhalb einer Matrix erfordert lediglich die Änderung ihres Werts. Nach der Generierung der Matrix und der Abfragenummer wählt der Code zufällig eine BFS-Abfrage oder eine Aktualisierungsabfrage aus und führt die entsprechende Operation aus. Das Ergebnis der BFS-Abfrage ist eine Zählung der miteinander verbundenen unbesetzten Zellen, beginnend mit der ausgewählten Zelle.

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

Ausgabe

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

Fazit

In diesem Artikel haben wir zwei Methoden besprochen, um die Anzahl verbundener nicht leerer Zellen in einer Matrix zu ermitteln und sie mithilfe von C/C++ zu aktualisieren. DFS-Algorithmus (Depth First Search) und Vereinigungssuche (Vereinigung disjunkter Mengen). Es ist wichtig, die zeitliche und räumliche Komplexität jeder Methode zu analysieren, bevor Sie die am besten geeignete Methode für einen bestimmten Anwendungsfall auswählen.

Das obige ist der detaillierte Inhalt vonAbfrage zum Aktualisieren der Anzahl verbundener nicht leerer Zellen in einer Matrix. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!