BFSとDFSの簡単な応用(二)
BFSとDFSの簡単な応用(二)
説明
キャンパスにはいくつかの小川といくつかの湖があります.今、私たちはそれらを池と見なしています.もし私たちの学校のどこかの地図があるとしたら、この地図にはここが池かどうかしか表示されていません.今、あなたの任務が来ました.コンピュータでこの地図にはいくつかの池があります.
入力
1行目は整数Nを入力し、N組のテストデータがあることを示す.
各グループのデータは、まず地図の行数m(0しゅつりょく
この地図の池の数を出力します.
各プールの横(上下左右4箇所)がプールであれば同じプールと見なすことに注意しましょう.
サンプル入力
サンプル出力
ACコード:
説明
キャンパスにはいくつかの小川といくつかの湖があります.今、私たちはそれらを池と見なしています.もし私たちの学校のどこかの地図があるとしたら、この地図にはここが池かどうかしか表示されていません.今、あなたの任務が来ました.コンピュータでこの地図にはいくつかの池があります.
入力
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
3ACコード:
#include<cstdio>
#define N 102
#define M 102
int map[N][M];
void search(int i,int j)
{
if(map[i][j-1])
{
map[i][j-1]=0;
search(i,j-1);
}
if(map[i][j+1])
{
map[i][j+1]=0;
search(i,j+1);
}
if(map[i-1][j])
{
map[i-1][j]=0;
search(i-1,j);
}
if(map[i+1][j])
{
map[i+1][j]=0;
search(i+1,j);
}
}
int main(int argc,char *argv[])
{
int t,n,m;
int i,j,count;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
count=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
scanf("%d",&map[i][j]);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(map[i][j])
{
count++;
map[i][j]=0;
search(i,j);
}
printf("%d
",count);
}
return 0;
}