水池數目（nyoj27）（BFS）

水池數目（nyoj27）（BFS）

水池數目

描述

南陽理工學院校園裡有一些小河和一些湖泊，現在，我們把它們通一看成水池，假設有一張我們學校的某處的地圖，這個地圖上僅標識了此處是否是水池，現在，你的任務來了，請用計算機算出該地圖中共有幾個水池。

輸入

第一行輸入一個整數N，表示共有N組測試數據
每一組數據都是先輸入該地圖的行數m(0 輸出

輸出該地圖中水池的個數。
要注意，每個水池的旁邊（上下左右四個位置）如果還是水池的話的話，它們可以看做是同一個水池。

樣例輸入

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
#include
int s[105][105];
int a[4]={0,0,1,-1};//向四個方向搜索。 
int b[4]={1,-1,0,0};
void bfs(int x,int y)
{
    int k,v,t;
	s[x][y]=0;
	for(k=0;k<4;k++)
	{
		v=x+a[k];
	    t=y+b[k];
		if(s[v][t])
		{
		   bfs(v,t);
	    }
	}
}
int main()
{
	int test,n,m,i,j,ans;
	scanf("%d",&test);
	while(test--)
	{
		scanf("%d%d",&m,&n);
		memset(s,0,sizeof(s));
		for(i=1;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			scanf("%d",&s[i][j]);
		}
		for(i=1,ans=0;i<=m;i++)
		{
			for(j=1;j<=n;j++)
			if(s[i][j])
			{
				bfs(i,j);
				ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}