二维矩阵中1所构成的块个数(孤岛问题)

  • Post author:
  • Post category:其他




二维矩阵中1所构成的块个数(孤岛问题),进行了总结。转载请注明链接,




有问题请及时联系博主:

Alliswell_WP



》问题描述:给定一个n*n的矩阵里面是0或1算出里面独立的0群组的数量。比如


0 0 1 1 1

0 1 1 1 0

1 1 1 1 0

1 0 1 1 1

1 1 1 1 1

答案:3。

》思路:虽然不是图,但是仍然可以用图的DFS思想。更没有必要用实现它对应的图。为了计数同时为了节省空间,把矩阵的元素本身来作为DFS时使用的标记量visited[ ]。

(1)采用深度优先搜索,遍历1在数组中的位置,对于遍历得到的1,先将其置位0再递归遍历该位置周围8个方向上是否为1,如果为1将其值变为0。这样顺次得到的1的个数就为最终结果;

(2)标注法:用count变量标注块的编号。从左到右从上到下遍历数组,对于值为1的位置,如果其左上,上,右上,左都为0,那么该位置的值变为count+1;否则该位置的值变为其左上,上,右上,左位置的值。最后根据count就可以求得块的个数。

(3)通过并查集解决;

上面方法的时间复杂度都为O(n)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
const int row = 5, col = 5;
//图的DFS,把所有连通结点标记为count
void DFS(int m[][col], int i, int j, int row, int col, int count)
{
    m[i][j] = count;
    if (i>0 && m[i - 1][j] == 0)
    {
        DFS(m, i - 1, j, row, col, count);
    }
    if (j>0 && m[i][j - 1] == 0)
    {
        DFS(m, i, j - 1, row, col, count);
    }
    if (i<row - 1 && m[i + 1][j] == 0)
    {
        DFS(m, i + 1, j, row, col, count);
    }
    if (j<col - 1 && m[i][j + 1] == 0)
    {
        DFS(m, i, j + 1, row, col, count);
    }
}

//对每个"为0且没有被标记"的结点进行DFS
int get_group(int m[][col], int row, int col)
{
    int count = 1; //01都被占用了,所以从2起始吧
    for (int i = 0; i<row; i++)
    {
        for (int j = 0; j<col; j++)
        {
            if (m[i][j] == 0)
            {
                count++;
                DFS(m, i, j, row, col, count);
            }
        }
    }
    return count - 1;//我是从2起始的
}

void display(int m[][5])
{
    for (int i = 0; i<row; i++)
    {
        for (int j = 0; j<col; j++)
            printf("%d ", m[i][j]);
        printf("\n");
    }

}
int main()
{
#if 0
    //手工输入矩阵的方式
int(*m)[col] = (int(*)[col])malloc(sizeof(int)*row*col); for (int i = 0; i<row; i++) for (int j = 0; j<col; j++) scanf("%d", &m[i][j]); #endif #if 1 //二维数组初始化的方式 int m[][col] = { { 0,0,1,1,1 }, { 0,1,1,1,0 }, { 1,1,0,1,0 }, { 1,0,1,0,0 }, { 1,0,0,0,1 } }; #endif display(m); printf("%d\n", get_group(m, row, col)); display(m); system("pause"); return 0; }


》代码优化:

改为手动输入二维矩阵的行数、列数和二维矩阵中0/1元素。

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include <malloc.h>
#include<iostream>

using namespace std;
//const int row = 5, col = 5;
static int row , col;
//图的DFS,把所有连通结点标记为count
void DFS(int **m, int i, int j, int row, int col, int count)
{
    m[i][j] = count;
    if (i>0 && m[i - 1][j] == 0)
    {
        DFS(m, i - 1, j, row, col, count);
    }
    if (j>0 && m[i][j - 1] == 0)
    {
        DFS(m, i, j - 1, row, col, count);
    }
    if (i<row - 1 && m[i + 1][j] == 0)
    {
        DFS(m, i + 1, j, row, col, count);
    }
    if (j<col - 1 && m[i][j + 1] == 0)
    {
        DFS(m, i, j + 1, row, col, count);
    }
}

//对每个"为0且没有被标记"的结点进行DFS
int get_group(int **m, int row, int col)
{
    int count = 1; //01都被占用了,所以从2起始吧
    for (int i = 0; i<row; i++)
    {
        for (int j = 0; j<col; j++)
        {
            if (m[i][j] == 0)
            {
                count++;
                DFS(m, i, j, row, col, count);
            }
        }
    }
    return count - 1;//我是从2起始的
}

void display(int **m, int row, int col)
{
    for (int i = 0; i<row; i++)
    {
        for (int j = 0; j<col; j++)
            printf("%d ", m[i][j]);
        printf("\n");
    }

}
int main()
{
#if 1
    //手工输入矩阵的方式
    cin >> row >> col;
    int **m;
    m = new int*[row];    //注意,int*[10]表示一个有10个元素的指针数组
    for (int i = 0; i < row; ++i)
    {
        m[i] = new int[col];
    }

    //int(*m)[col] = (int(*)[col])malloc(sizeof(int)*row*col);
    for (int i = 0; i<row; i++)
        for (int j = 0; j<col; j++)
            scanf("%d", &m[i][j]);
#endif

#if 0
    //二维数组初始化的方式
    int m[][col] = { { 0,0,1,1,1 },
    { 0,1,1,1,0 },
    { 1,1,0,1,0 },
    { 1,0,1,0,0 },
    { 1,0,0,0,1 } };
#endif

    display(m,row, col);
    printf("%d\n", get_group(m, row, col));
    display(m, row, col);
    for (int i = 0; i < col; i++)
    {
        delete[] m[i];
    }
    delete[] m;
    system("pause");
    return 0;
}



二维矩阵中1所构成的块个数(孤岛问题),进行了总结。转载请注明链接,




有问题请及时联系博主:

Alliswell_WP


题目:给定一个n*n的矩阵里面是0或1算出里面独立的0群组的数量。比如

0 0 1 1 1

0 1 1 1 0

1 1 1 1 0

1 0 1 1 1

1 1 1 1 1

答案:3。

思路:虽然不是图,但是仍然可以用图的DFS思想。更没有必要用实现它对应的图。为了计数同时为了节省空间,把矩阵的元素本身来作为DFS时使用的标记量visited[ ]。



版权声明:本文为qq_21685903原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。