查询以更新的矩阵中连接的非空单元格的数量

矩阵可以被认为是按行和列组织的单元格的集合。每个单元格可以包含一个值，该值可以为空或非空。在计算机编程中，矩阵通常用于表示二维网格中的数据。

在本文中，我们将讨论如何有效地计算矩阵中连接的非空单元格的数量，同时考虑到矩阵可能的更新。我们将探索解决此问题的不同方法，并提供真实的代码示例来演示实现。

语法

使用 C/C++ 查询矩阵中连接的非空单元格数量并进行更新的基本语法可以定义如下 -

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

其中matrix是输入的“矩阵”，“rows”和“cols”分别表示矩阵中的行数和列数。函数“queryCount”返回一个整数值，表示矩阵中连接的非空单元格的数量。

算法

为了解决这个问题，我们可以遵循以下算法 -

第 1 步 - 将变量“count”初始化为 0，这将存储连接的非空单元格的计数。

第 2 步 - 迭代矩阵中的每个单元格。

步骤 3 - 对于每个单元格，检查它是否非空（即包含非空值）。

第 4 步 - 如果单元格非空，则将“计数”增加 1。

步骤 5 - 检查单元格是否有任何非空的相邻单元格。

第 6 步 - 如果相邻单元格非空，则将“计数”增加 1。

步骤 7 - 对所有相邻单元格重复步骤 5-6。

第 8 步 - 8：迭代矩阵中的所有单元格后，返回“计数”作为最终结果。

方法

• 方法 1 - 解决此问题的一种常见方法是使用深度优先搜索 (DFS) 算法

• 方法 2 - 实现查询以查找具有更新的矩阵中连接的非空单元格计数的另一种方法是使用广度优先搜索 (BFS) 算法。

方法 1

在这种方法中，DFS 算法涉及递归遍历矩阵并跟踪访问过的单元以避免重复计数。

示例 1

此方法在二维矩阵上执行深度优先搜索。矩阵的维数、单元格值和查询次数都是随机确定的。 countConnectedCells 子例程执行 DFS 并返回互连的非空单元格的计数，从位于指定行和列的单元格开始。 updateCell 函数更新矩阵中单元格的值。主函数使用当前时间启动随机种子，然后生成随机矩阵大小和元素，然后是随机数量的查询。对于每个查询，代码随机选择计数查询 (1) 或更新查询 (2) 并执行相应的操作。如果查询的类型为 1，则调用 countConnectedCells 函数来确定互连的非空单元格的计数并打印结果。如果查询类型为2，则调用updateCell函数调整指定单元格的值。

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

输出

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

方法2

在这种方法中，广度优先搜索（BFS）是另一种图遍历算法，可用于查找矩阵中连接的非空单元格的数量。在 BFS 中，我们从给定的单元开始，以广度优先的方式（即逐层）探索其所有相邻单元。我们使用队列来跟踪要访问的单元格，并标记已访问的单元格以避免多次计数。

示例 2

该代码构成了一个在二维矩阵上执行广度优先搜索算法的软件。矩阵的维数、单元格值和查询数量是任意生成的。该代码包含两个子例程：一个用于执行 BFS，另一个用于调整矩阵内的单元。

BFS 操作从随机选择的小区开始，并检查其相邻小区以确定它们是否互连且未被占用。如果是这样，它们将被附加到队列中并以类似的方式进行处理。更新矩阵内的单元仅涉及更改其值。生成矩阵和查询数量后，代码随机选择 BFS 查询或更新查询并执行适当的操作。 BFS 查询的结果是从所选单元格开始的互连未占用单元格的计数。

代码

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

输出

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

结论

在本文中，我们讨论了两种使用 C/C++ 查找矩阵中连接的非空单元格数量并进行更新的方法。深度优先搜索（DFS）算法和并集查找（不相交集并集）。在为特定用例选择最合适的方法之前，分析每种方法的时间复杂度和空间复杂度非常重要。