数据结构
网络
关系型数据库管理系统 (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 次查看
