nyoj 24プール数


プール数
時間制限:3000 ms|メモリ制限:65535 KB
難易度:4
説明
南陽理工学院のキャンパスには小川と湖があります.今、私たちはそれらを池と見なしています.もし私たちの学校のどこかの地図があるとしたら、この地図にはここが池かどうかしか表示されていません.今、あなたの任務が来ました.コンピュータでこの地図にはいくつかの池があります.
入力
1行目は整数Nを入力し、N組のテストデータがあることを示す.
各グループのデータは、まず地図の行数m(0しゅつりょく
この地図の池の数を出力します.
各プールの横(上下左右4箇所)がプールであれば同じプールと見なすことに注意しましょう.
サンプル入力
2
3 4
1 0 0 0
0 0 1 1
1 1 1 0
5 5
1 1 1 1 0
0 0 1 0 1
0 0 0 0 0
1 1 1 0 0
0 0 1 1 1
サンプル出力
2
3
                 ( , , , )            ,                       

#include<stdio.h>
#include<string.h>
#define MAX 110
int s[MAX][MAX];
int n,m;
void dfs(int x,int y)
{
    if(0<x&&x<=n&&0<y&&y<=m&&s[x][y])//         n*m   ,            
    {                                //          
        s[x][y]=0;//         
        dfs(x-1,y);  //                      
        dfs(x,y-1);//                       
        dfs(x+1,y);  //          
        dfs(x,y+1);// 
    }
    return ;
}
int main()
{
    int j,i,sum,t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&s[i][j]);
            }
        }
        sum=0;
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                if(s[i][j])
                {
                    dfs(i,j);
                    sum++;
                }
            }
        }
        printf("%d
",sum); } return 0; }