查詢以更新的矩陣中連接的非空單元格的數量

矩陣可以被認為是按行和列組織的單元格的集合。每個單元格可以包含一個值，該值可以為空或非空。在電腦程式設計中，矩陣通常用於表示二維網格中的資料。

在本文中，我們將討論如何有效地計算矩陣中連接的非空單元格的數量，同時考慮到矩陣可能的更新。我們將探索解決此問題的不同方法，並提供真實的程式碼範例來演示實作。

文法

使用 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）演算法和並集查找（不相交集並集）。在為特定用例選擇最合適的方法之前，分析每種方法的時間複雜度和空間複雜度非常重要。

以上是查詢以更新的矩陣中連接的非空單元格的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！