数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究更新矩阵后查找连接的非空单元格数量的查询
矩阵可以被认为是按行和列组织的单元格集合。每个单元格可以包含一个值，该值可以为空或非空。在计算机编程中，矩阵通常用于表示二维网格中的数据。
在本文中，我们将讨论如何有效地计算矩阵中连接的非空单元格的数量，同时考虑对矩阵的可能更新。我们将探讨解决此问题的不同方法，并提供真实的代码示例来演示实现。
语法
使用 C/C++ 查询更新后矩阵中连接的非空单元格数量的基本语法可以定义如下：
int queryCount(int matrix[][MAX_COLS], int rows, int cols);
其中 matrix 是输入“矩阵”，'rows' 和 'cols' 分别表示矩阵的行数和列数。函数 'queryCount' 返回一个整数值，表示矩阵中连接的非空单元格的数量。
算法
为了解决这个问题，我们可以遵循以下算法：
步骤 1 - 将变量 'count' 初始化为 0，它将存储连接的非空单元格的数量。
步骤 2 - 遍历矩阵中的每个单元格。
步骤 3 - 对于每个单元格，检查它是否是非空的（即，包含除空值以外的值）。
步骤 4 - 如果单元格是非空的，则将 'count' 加 1。
步骤 5 - 检查单元格是否具有任何也非空的相邻单元格。
步骤 6 - 如果相邻单元格是非空的，则将 'count' 加 1。
步骤 7 - 对所有相邻单元格重复步骤 5-6。
步骤 8 - 8：遍历完矩阵中的所有单元格后，返回 'count' 作为最终结果。
方法
方法 1 - 解决此问题的一种常见方法是使用深度优先搜索 (DFS) 算法
方法 2 - 实现查询以查找更新后矩阵中连接的非空单元格数量的另一种方法是使用广度优先搜索 (BFS) 算法。
方法 1
在这种方法中，DFS 算法涉及递归遍历矩阵并跟踪已访问的单元格以避免重复计数。
示例 1
此方法对二维矩阵执行深度优先搜索。矩阵的维度、单元格值和查询数量都是随机确定的。countConnectedCells 子例程执行 DFS 并返回从指定行和列处的单元格开始的互连非空单元格的数量。updateCell 函数更新矩阵中单元格的值。main 函数使用当前时间初始化随机种子，然后生成随机的矩阵大小和元素，然后生成随机数量的查询。对于每个查询，代码随机选择计数查询 (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) 算法和并查集 (不相交集联合)。在为特定用例选择最合适的方法之前，务必分析每种方法的时间复杂度和空间复杂度。
74 次查看
