Query to update the number of connected non-empty cells in a matrix

A matrix can be thought of as a collection of cells organized in rows and columns. Each cell can contain a value, which can be empty or non-empty. In computer programming, matrices are often used to represent data in a two-dimensional grid.

In this article, we will discuss how to efficiently count the number of connected non-empty cells in a matrix, taking into account possible updates to the matrix. We'll explore different ways to solve this problem and provide real-world code examples to demonstrate implementation.

grammar

The basic syntax for querying the number of connected non-empty cells in a matrix and updating it using C/C can be defined as follows -

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

Where matrix is ​​the input "matrix", "rows" and "cols" represent the number of rows and columns in the matrix respectively. The function "queryCount" returns an integer value representing the number of connected non-empty cells in the matrix.

algorithm

To solve this problem, we can follow the following algorithm -

Step 1 - Initialize the variable "count" to 0, this will store the count of connected non-empty cells.

Step 2 - Iterate over each cell in the matrix.

Step 3 - For each cell, check whether it is non-empty (i.e. contains a non-null value).

Step 4 - If the cell is not empty, increase the Count by 1.

Step 5 - Check if the cell has any non-empty adjacent cells.

Step 6 - If the adjacent cell is not empty, increase the Count by 1.

Step 7 - Repeat steps 5-6 for all adjacent cells.

Step 8 - 8: After iterating through all cells in the matrix, return "count" as the final result.

method

• Method 1 - A common way to solve this problem is to use the Depth First Search (DFS) algorithm

• Method 2 - Another way to implement a query to find the count of non-empty cells with joins in an updated matrix is ​​to use the Breadth-First Search (BFS) algorithm.

method 1

In this approach, the DFS algorithm involves recursively traversing the matrix and keeping track of visited cells to avoid double counting.

Example 1

This method performs a depth-first search on a two-dimensional matrix. The dimensions, cell values, and number of queries of the matrix are randomly determined. The countConnectedCells subroutine performs DFS and returns a count of connected, non-empty cells, starting with the cell at the specified row and column. The updateCell function updates the value of a cell in a matrix. The main function starts a random seed using the current time, then generates a random matrix size and elements, followed by a random number of queries. For each query, the code randomly selects a count query (1) or an update query (2) and performs the appropriate action. If the query's type is 1, the countConnectedCells function is called to determine the count of connected, non-empty cells and prints the result. If the query type is 2, call the updateCell function to adjust the value of the specified cell.

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

Output

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

Method 2

In this approach, Breadth First Search (BFS) is another graph traversal algorithm that can be used to find the number of connected non-empty cells in a matrix. In BFS, we start from a given cell and explore all its neighboring cells in a breadth-first manner (i.e., layer-by-layer). We use a queue to keep track of which cells are being accessed, and mark cells that have been accessed to avoid multiple counts.

Example 2

This code constitutes a software that performs a breadth-first search algorithm on a two-dimensional matrix. The dimensions of the matrix, cell values, and number of queries are generated arbitrarily. The code contains two subroutines: one to perform BFS and another to adjust the cells within the matrix.

BFS operation starts with a randomly selected cell and checks its neighboring cells to determine if they are interconnected and unoccupied. If so, they will be appended to the queue and processed in a similar manner. Updating a cell within a matrix only involves changing its value. After generating the matrix and query number, the code randomly selects a BFS query or an update query and performs the appropriate operation. The result of the BFS query is a count of interconnected unoccupied cells starting from the selected cell.

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

Output

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

in conclusion

In this article, we discussed two methods of using C/C to find the number of connected non-empty cells in a matrix and update them. Depth First Search (DFS) algorithm and union search (union of disjoint sets). It is important to analyze the time complexity and space complexity of each method before choosing the most appropriate method for a specific use case.

The above is the detailed content of Query to update the number of connected non-empty cells in a matrix. For more information, please follow other related articles on the PHP Chinese website!