问题 F: Vegetable and Park
时间限制: 1 Sec 内存限制: 128 MB题目描述
毕业后，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<stdio.h>
#include<string.h>
#define M 100+2
int a[M][M];
int move[][2]={
{1,0},{-1,0},{0,1},{0,-1}}; // 一个点移动的四个方向
void dfs(int x,int y)
{
a[x][y]=0;
for(int i=0;i<4;i++)
{
int nx=x+move[i][0];
int ny=y+move[i][1];
if(a[nx][ny])
{
bfs(nx,ny);
}
}
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int x,y;
scanf("%d%d",&x,&y);
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
scanf("%d",&a[i][j]);
}
}
int num=0;
for(int i=1;i<=x;i++)
{
for(int j=1;j<=y;j++)
{
if(a[i][j])
{
dfs(i,j);
num++;
}
}
}
printf("%d\n",num);
}
return 0;}