資料結構
網路
關係型資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究矩陣所有連通非空單元格的大小
在這個問題中，我們將找到所有非空連通單元格的集合的大小。
我們將學習兩種不同的方法來查詢矩陣所有非空連通單元格的大小。在第一種方法中，我們將使用廣度優先搜尋演算法，在第二種方法中，我們將使用深度優先搜尋演算法遍歷矩陣並找到所有非空連通單元格的大小。
問題陳述 - 我們給定了一個包含只有 0 和 1 的二維陣列 matrix[][]。這裡，0 表示空單元格，1 表示非空單元格。我們需要找到非空連通單元格的大小。
注意 - 我們可以說兩個單元格是連通的，如果它們在水平或垂直方向上彼此相鄰。
示例
輸入
{{0, 1, 0, 0, 0},
{0, 1, 1, 1, 1},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 0, 1, 1, 1}};
輸出
7 2 3
解釋
第一個連通集包含 matrix[0][1]、matrix[1][1]、matrix[1][2]、matrix[1][3]、matrix[1][4]、matrix[2][3] 和 matrix[2][4] 單元格。
第二個連通集包含 matrix[2][0] 和 matrix[3][0] 單元格。
第三個連通集包含 matrix[4][2]、matrix[4][3] 和 matrix[4][4] 單元格。
輸入
{{0, 1, 0, 0, 0},
{0, 1, 1, 1, 1},
{0, 0, 0, 1, 1},
{0, 0, 0, 1, 0},
{0, 0, 1, 1, 1}};
輸出
11
解釋 - 矩陣的所有非空單元格都是連通的。
方法 1
在這種方法中，我們將使用 BFS 技術遍歷每個矩陣單元格。如果我們找到非空單元格，我們將從該單元格開始 BFS 遍歷以找到所有連線節點的數量。此外，我們將訪問過的節點更新為 0，因為我們不想多次計算同一個節點。
演算法
步驟 1 - 使用兩個巢狀迴圈遍歷矩陣。
步驟 2 - 如果當前單元格的值為 1，則呼叫 BFSTraversal() 函式以獲取當前單元格所有連通單元格的大小。
步驟 2.1 - 在 BFSTraversal() 函式中，將 'res' 初始化為 0 以儲存大小。另外，定義用於 BFS 遍歷的佇列。
步驟 2.2 - 將當前單元格的座標插入佇列
步驟 2.3 - 在佇列不為空時進行遍歷。
步驟 2.3.1 - 從迴圈內的佇列中獲取第一對。
步驟 2.3.2 - 從第一對中獲取行和列值。此外，檢查邊界驗證以確保行和列對是有效的矩陣單元格。
步驟 2.3.3 - 如果 matrix[row][col] 為 0，則繼續執行迴圈的下一輪迭代。否則，將 matrix[col][row] 更新為 0，並將 'res' 加 1。
步驟 2.3.4 - 將所有 4 個相鄰元素的行和列對插入佇列。
步驟 2.4 - 返回 'res' 值。
步驟 3 - 將 BFSTraversal() 函式返回的值插入 'ans' 列表。
步驟 4 - 列印 'ans' 列表的所有元素。
示例
#include <bits/stdc++.h>
using namespace std;
int BFSTraversal(vector<vector<int>> &matrix, int p, int q, int rows, int cols) {
int res = 0;
// Queue to store the cells
queue<pair<int, int>> que;
// Insert the starting point
que.push({p, q});
while (!que.empty()) {
// Get the first element from the queue
auto first = que.front();
que.pop();
int row = first.first, col = first.second;
// Boundry validation
if (row < 0 || col < 0 || row > rows - 1 || col > cols - 1)
continue;
// For visited elements
if (matrix[row][col] == 0)
continue;
// For non-visited elements
if (matrix[row][col] == 1) {
// Update matrix cell
matrix[row][col] = 0;
res++;
}
// Traverse all neighbors
que.push({row + 1, col});
que.push({row - 1, col});
que.push({row, col + 1});
que.push({row, col - 1});
}
return res;
}
void printSizeOfConnected(vector<vector<int>> matrix) {
// To store sizes
vector<int> ans;
int rows = matrix.size();
int cols = matrix[0].size();
for (int p = 0; p < rows; ++p) {
for (int q = 0; q < cols; ++q) {
// If the current cell is not visited
if (matrix[p][q] == 1) {
// To get the total number of connected nodes to the current node
int sz = BFSTraversal(matrix, p, q, rows, cols);
ans.push_back(sz);
}
}
}
cout << "The sizes of the connected nodes are ";
for (int val : ans)
cout << val << " ";
}
int main() {
vector<vector<int>> matrix = {{0, 1, 0, 0, 0},
{0, 1, 1, 1, 1},
{1, 0, 0, 1, 1},
{1, 0, 0, 0, 0},
{0, 0, 1, 1, 1}};
printSizeOfConnected(matrix);
return 0;
}
輸出
The sizes of the connected nodes are 7 2 3
時間複雜度 - O(row*col) 以遍歷矩陣的所有單元格。
空間複雜度 - O(row*col) 以在佇列中儲存對。
方法 2
在這種方法中，我們將使用 DFS 遍歷來查詢非空連通單元格的大小。
演算法
步驟 1 - 定義 'vis' 列表以跟蹤矩陣的特定單元格是否已訪問。
步驟 2 - 使用兩個巢狀迴圈開始遍歷矩陣。
步驟 3 - 如果單元格值為 1 且未訪問，則呼叫 performDFS() 函式以查詢連通非空集的大小。
步驟 3.1 - 在 performDFS() 函式中，將 vis[p][q] 更新為 1，並將 'sz' 加 1。
步驟 3.2 - 定義包含垂直和水平方向的 dirX[] 和 dirY[] 陣列。
步驟 3.3 - 開始遍歷 dirX[] 和 dirY[] 陣列以在每個方向上移動。
步驟 3.4 - 檢查更新的行和列值的邊界驗證。此外，單元格值為 1 且未訪問，因此對更新的座標執行 performDFS() 函式。
步驟 4 - 列印 'sz' 值。
示例
#include <bits/stdc++.h>
using namespace std;
void performDFS(vector<vector<int>> &matrix, vector<vector<int>> &vis, int p, int q, int *sz) {
// Current node is visited
vis[p][q] = 1;
(*sz)++;
int dirX[] = {-1, 0, 1, 0};
int dirY[] = {0, 1, 0, -1};
// Traverse in all adjacent directions
for (int k = 0; k < 4; k++) {
int temp1 = p + dirX[k];
int temp2 = q + dirY[k];
// Validating the boundary conditions and checking if the current cell is non-visited
if (temp1 >= 0 && temp1 < matrix.size() && temp2 >= 0 && temp2 < matrix[0].size() && matrix[temp1][temp2] && !vis[temp1][temp2]) {
// Making recursive calls for all nodes
performDFS(matrix, vis, temp1, temp2, sz);
}
}
}
int main() {
vector<vector<int>> matrix = {
{1, 0, 1, 0},
{1, 0, 0, 1},
{0, 1, 0, 0},
{1, 1, 0, 1}};
int rows = matrix.size();
int cols = matrix[0].size();
vector<vector<int>> vis(rows, vector<int>(cols, 0));
cout << "The sizes of the connected nodes are ";
// Traverse the matrix and count the size of each connected component
for (int p = 0; p < rows; p++) {
for (int q = 0; q < cols; q++) {
if (matrix[p][q] && !vis[p][q]) {
int sz = 0;
performDFS(matrix, vis, p, q, &sz);
cout << sz << " ";
}
}
}
return 0;
}
輸出
The sizes of the connected nodes are 2 1 1 3 1
時間複雜度 - O(row*col)
空間複雜度 - O(1)
BFS 和 DFS 遍歷給出相同的結果。但是，DFS 遍歷不需要動態記憶體。每當程式設計師需要查詢最短路徑或類似內容時，建議使用 BFS 遍歷。否則，程式設計師可以使用 BFS 或 DFS 遍歷中的任何一個。
99 次檢視
