Vegetable and Park
时间限制: 1 Sec 内存限制: 128 MB
提交: 12 解决: 10
题目描述
毕业后，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>//这是一道DFS的模板题
#include<cstring>
int arr[120][120];
int l,w;
void dfs(int x,int y)
{if(arr[x][y]==1) return ; if(x<0 || x>=w || y<0 || y>=l) return ;//超过边界不满足，返回空 arr[x][y]=1;//每次走过得到路变成 1 dfs(x-1,y);//这里运用了递归的思想，跟bfs不同的是这是一行一行的查找，即深度搜索，而bfs即广度搜索是向四周查找 dfs(x+1,y);dfs(x,y-1); dfs(x,y+1);
}
int main()
{int t;scanf("%d",&t);while(t--){scanf("%d%d",&w,&l);memset(arr,0,sizeof(arr));for(int i=0;i<w;i++)for(int j=0;j<l;j++){scanf("%d",&arr[i][j]);}int flag=0;for(int i=0;i<w;i++){for(int j=0;j<l;j++){if(arr[i][j]==0){flag++;dfs(i,j);// 每次走过之后就把相连区域内所有的0都变成了1，所以继续扫描发现得到新的0肯定是另外一个区域的 }}}printf("%d\n",flag);}return 0;}