题目描述

输入一个只包含0和1的二维数组，上下左右和对角相邻的1组成一个区块，0不形成区块，求数组中的区块个数。

输入格式
第一行输入两个正整数N和M，N表示数组行数，M表示数组列数。

接下来N行，每行表示数组对应的一行，每行包含M个整数，整数之间用空格隔开。

输出格式
输出一个整数，表示数组中区块的个数。

数据范围
0≤N,M,N∗M≤106

输入样例

3 3
0 1 0
1 0 0
1 0 1

输出样例

2

算法1

(dfs) $O(nm)$

题目N*M <= 1e6
并没有确定NM大小，所以不能直接存

1.
将二维数组映射为一维数组
对于a[ i ][ j ] 在一维数组中对应为a[ i * M + j ];

2.
使用
vector< vector< int > >

C++ 代码

//一维数组
#include<bits/stdc++.h>
using namespace std;

const int maxn = 1000010;

int a[ maxn ];
int n, m, tmp;

void dfs( int x, int y )
{
    a[ x * m + y ] = 0;
    for( int i = -1; i <= 1; i ++ )
    for( int j = -1; j <= 1; j ++ )
    {
        int nx = x + i;
        int ny = y + j;
        if( nx < 0 || nx >= n || ny < 0 || ny >= m || a[ nx * m + ny ] == 0 ) continue;
        dfs( nx, ny );
    }
}

int main()
{
    scanf( "%d %d", &n, &m );
    for( int i = 0; i < n; i ++ )
    for( int j = 0; j < m; j ++ )
    {
        scanf( "%d", &tmp );
        a[ i * m + j ] = tmp;
    }
    int res = 0;
    for( int i = 0; i < n; i ++ )
    for( int j = 0; j < m; j ++ )
    {
        if( a[ i * m + j ] )
        {
            res ++;
            dfs( i, j );
        }
    }
    printf( "%d\n", res );
    return 0;
}

//vector< vector< int > >
#include<bits/stdc++.h>
using namespace std;

int N, M;

vector< vector< int > > Maps;

void dfs( int x, int y )
{
    Maps[ x ][ y ] = 0;
    for( int i = -1; i <= 1; i ++ )
    for( int j = -1; j <= 1; j ++ )
    {
        if( i == 0 && j == 0 ) continue;
        int nx = x + i;
        int ny = y + j;
        if( nx >= N || nx < 0 || ny >= M || ny < 0 || Maps[ nx ][ ny ] == 0 ) continue;
        dfs( nx, ny ); 
    }
}

int main()
{
    scanf( "%d %d", &N, &M );
    Maps.resize( N );
    for( int i = 0; i < N; i ++ ) Maps[ i ].resize( M );

    for( int i = 0; i < N; i ++ )
    for( int j = 0; j < M; j ++ ) scanf( "%d", &Maps[ i ][ j ] );

    int goal = 0;
    for( int i = 0; i < N; i ++ )
    for( int j = 0; j < M; j ++ )
    {
        if( Maps[ i ][ j ] )
        {
            goal ++;
            dfs( i, j );
        }
    }
    printf( "%d\n", goal );
    return 0;
}