C++ 矩阵中所有连通非空单元的大小

在这个问题中，我们将找到所有非空连通单元集合的大小。

我们将学习两种不同的方法来找到矩阵中所有非空连通单元的大小。在第一种方法中，我们将使用广度优先搜索算法，而在第二种方法中，我们将使用深度优先搜索算法遍历矩阵并找到所有非空连通单元的大小。

问题说明 −我们给出矩阵[][]的二维数组，只包含0和1。这里，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（行 * 列）

空间复杂度 – O（1）

BFS和DFS遍历结果相同。然而，DFS遍历不占用动态内存。当程序员需要找到最短路径或类似的东西时，建议使用BFS遍历。否则，程序员可以使用BFS或DFS遍历之一。