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
時間制限: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;
}