資料結構
網路
關係型資料庫管理系統 (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 次檢視
