信息学奥赛一本通T1335：连通块

【题目描述】

一个n * m的方格图，一些格子被涂成了黑色，在方格图中被标为1，白色格子标为0。问有多少个四连通的黑色格子连通块。四连通的黑色格子连通块指的是一片由黑色格子组成的区域，其中的每个黑色格子能通过四连通的走法（上下左右），只走黑色格子，到达该联通块中的其它黑色格子。

【输入】

第一行两个整数n,m(1≤n,m≤100)，表示一个n * m的方格图。

接下来n行，每行m个整数，分别为0或1，表示这个格子是黑色还是白色。

【输出】

一行一个整数ans，表示图中有ans个黑色格子连通块。

【输入样例】

3 3
1 1 1
0 1 0
1 0 1

【输出样例】

3

【源程序】

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<queue>
#include<vector>
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define N 101
#define MOD 123
#define E 1e-6
using namespace std;
struct node{
    int x;
    int y;
}q[10100],p;
int a[N][N],vis[N][N];
int next[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>a[i][j];

    int cnt=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(vis[i][j]==0&&a[i][j]==1)
            {
                cnt++;
                vis[i][j]=1;
                int head=1,tail=1;
                q[tail].x=i;
                q[tail].y=j;

                tail++;
                while(head<tail)
                {
                    p=q[head];
                    for(int k=0;k<4;k++)
                    {
                        int nx=p.x+next[k][0];
                        int ny=p.y+next[k][1];
                        if(vis[nx][ny]==0&&a[nx][ny]==1)
                        {
                            vis[nx][ny]=1;
                            q[tail].x=nx;
                            q[tail].y=ny;
                            tail++;
                        }
                    }
                    head++;
                }
            }

    cout<<cnt<<endl;
    return 0;
}

信息学奥赛一本通T1335：队列 连通块 归属于 队列，更多同类题解源程序见：队列 和 连通块