题目描述

毕业后，Vegetable在一家建筑公司找到了工作。他所在的城市将要进行整修，要求把所有空地修成公园。

市区是一个N*M的矩形，Vegetable拿到了该市的地图，现在判断共要修几处公园？

注意：在一片空地上，它上下左右的位置是空地，则视为统一片空地。

输入

共有T组测试数据，每组测试数据包含一组N和M(0<n,m<=100)，分别表示市区的长和宽。

接下来N行每行有M个数（1代表楼房，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<cstdio>
const int MAX=105;
int N,M;
int field[MAX][MAX];  
void dfs(int x,int y){
	field[x][y]=1;     
  for(int nx=x-1,ny=y;nx<=x+1;nx+=2)
  if(nx>=0&&nx<N&&ny>=0&&ny<M&&field[nx][ny]==0)
         dfs(nx,ny);
   for(int ny=y-1,nx=x;ny<=y+1;ny+=2)
   if(nx>=0&&nx<N&&ny>=0&&ny<M&&field[nx][ny]==0)
         dfs(nx,ny);
 	return ;
}
void solve(){
	int ans=0;
	for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(field[i][j]==0)
			{  
			   dfs(i,j);
			   ans++;
			}
		}
	}
	printf("%d\n",ans);
}
int main(){
	int t;
	scanf("%d",&t);
	while(t--){
	int p,q;
	scanf("%d%d",&N,&M);
	for(p=0;p<N;p++){
		for(q=0;q<M;q++){
		scanf("%d",&field[p][q]);
	}
 
	}
	solve(); }
	return 0;
}