首页 > 代码库 > shu-Problem H: 建筑物中的套间
shu-Problem H: 建筑物中的套间
跟hdu1241很相似的一个题目:
Problem H: 建筑物中的套间
建筑物的平面图标明墙在什么地方。该建筑物最初的平面图的外边界是无破损的围墙。里面也没有门,仅有的是墙内的一个开口,可以从一个房间走到另一个房间。套间是若干彼此相连通的房间的组合,各套间仅由墙隔开。本问题要求:
(a)计算建筑物图中套间的数目;
(b)计算最大的套间的面积。
为简化问题,建筑物的平面分成方格,所有墙形成了边界。套间的面积是套间内房间中所有方块的总数,不考虑围墙。下图是平面图的例子。每个正方形是一个方块,白色方块表示空地,而黑色方块表示墙。该建筑物中,有4个套间,最大的套间,其面积是58。
Input
输入有多组数据。每组的第一行有两个正整数M和N,(0 < M<= 500,0 < N<= 500),M、N分别表示平面图的行和列数。接着有M行,每一行由N个0、1构成的序列,之间用空格隔开,0表示空地(1块白色方块),1表示墙(1块黑色方块)。建筑物的外边界总是由无破损的墙围成。对应于上图的平面图的输入如下输入样例所示。
Output
对每组输入数据信息,一行上输出2个数,即套间的数目与最大的套间面积,之间用一个空格隔开。
Sample Input
15 19
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 0 0 0 0 1 0 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 1
1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1
1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1
1 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Sample Output
4 58
HINT
#include<iostream>#include<string.h>#include<algorithm>#include<cstdlib>#include<cstdio>using namespace std;int sum,ans;int m,n;int map[505][505];bool visit[505][505];int dir[4][2]={-1,0,0,-1,0,1,1,0};int isin(int x,int y){ return x>=0&&x<m&&y>=0&&y<n;}int dfs(int i,int j){ visit[i][j]=false; int num=0; for(int k=0;k<4;k++) { int ii,jj; ii=i+dir[k][0]; jj=j+dir[k][1]; if(map[ii][jj]==0&&ii>=0&&ii<m&&jj>=0&&jj<n&&visit[ii][jj]) { num +=dfs(ii,jj); } } return num+1;}int main(){ int i,j; while(scanf("%d%d",&m,&n)!=EOF) { for(i=0;i<m;i++) for(j=0;j<n;j++) cin>>map[i][j]; memset(visit,true,sizeof(visit)); sum=0;ans=0; for(i=0;i<m;i++) for(j=0;j<n;j++) { if(map[i][j]==0&&visit[i][j]) { sum++; ans= max(ans,dfs(i,j)); } } cout<<sum<<‘ ‘<<ans<<endl; } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。