描述
给定一个n行m列的二值图像,0为背景,1为前景物,请计算该图像中有多少块区域块(由连接的1构成),并输出
最大的区域块的像点数。
同一个区域块中的点要么是连接的,要么是存在包围关系。
判断两个区域是否连接采用四邻域判定,即一点仅与它的上下左右四个点相连;
判断两个区域是否存在包含关系即一个区域被另一个区域完全包围,如下所示,中间的两个1被外面的16个1完全包围(中间的两个1不
存在通往外界的四邻域通路)
00000000
00111110
00100001
00101101
00100001
00111110
00000000
存在包围关系的两个区域属于同一个区域块
输入格式
第一行两个正整数,n和m(n,m<=100)
此后n行,每行m个0或1
输出格式
输出区域块数和最大区域块像点数,数字中间以一个空隔分隔
输入样例
6 8
01111110
01000010
01011010
01000010
01111110
00000001
输出样例
2 20
首先主要思路就是用漫水法,对每一个连通域进行染色,染色结束之后,首先先对外层那一圈的0进行收集,非零元素不收集,并且将其标记,标记为为外层轮廓,是大轮廓,是可以包围内部的轮廓的,然后对这一圈0进行广度优先搜索,在广度优先搜索的时候就会对这一圈0周围的大轮廓都找出来,只要找到了,就标记,然后最后扫一下二维数组,对于扫到的数字判断是否属于大轮廓,大轮廓不管它,小轮廓的话自然就要被并到它所属的大轮廓里面了(注意:题目给的数据是很弱的,实际上我们如果直接向(任意一个方向)去检测它最近的一个不同连通域,是有很大问题的,但是题目没有这种数据,就先不管,后面再补上debug的代码),并进去的操作就是把小轮廓的color设置为大轮廓的color,最后结算就可以了
我的代码中在广度优先搜索的时候顺便把连通域的邻接表给建好了,在后面弄合并的时候效率比较高,对于标记数组的话采用map的话比较节省空间.
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <utility> #include <map> using namespace std; const int N=100+5; const int M=N*N; char temp[N][N]; int a[N][N]; int book[N][N]; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; struct data{ int x; int y; }; struct data q[M]; vector< vector< pair<int,int> > > dataMap; map <int,bool> idMap; int main() { //基础数据处理 ios::sync_with_stdio(false); int n,m;cin>>n>>m; for(int i=0;i<n;i++){ cin>>temp[i]; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ a[i][j]=(temp[i][j]-'0'); } } //BFS过程中建立一个邻接表 int head=0,tail=0,color=2; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(book[i][j]==0 && a[i][j]!=0){ //新节点入队,头节点出队,标记 a[i][j]=color; q[tail].x=i;q[tail].y=j; tail++; book[i][j]=1; //将点输入到pair pair<int,int> temp; vector<pair<int,int> > vecTemp; temp.first=i;temp.second=j; vecTemp.push_back(temp); while(head!=tail){ for(int k=0;k<4;k++){ int tx=q[head].x+dir[k][0]; int ty=q[head].y+dir[k][1]; if(tx<0 || tx>=n || ty<0 || ty>=m){ continue; } if(a[tx][ty]!=0 && book[tx][ty]==0 ){ book[tx][ty]=1; q[tail].x=tx; q[tail].y=ty; a[tx][ty]=color; tail++; temp.first=tx;temp.second=ty; vecTemp.push_back(temp); } } head++; }//执行到这里就是一次扩列结束(同个面积的检测结束) dataMap.push_back(vecTemp);//邻接表建立成功 color++; } } } //cout<<color<<endl; //提取外轮廓 struct data q2[M];//这是后面用来做外轮廓广搜的 head=tail=0; memset(book,0,sizeof(book)); for(int i=0;i<n;i++){//竖向,左侧和右侧都要检测零,遇到零,将其入队,表示下面要开始广搜的其中一个起点,否则就代表是个外轮廓的起点,我们将其标记为外轮廓 if(a[i][0]==0){ q2[tail].x=i; q2[tail++].y=0; }else{ idMap[ a[i][0] ] =true; } if(a[i][m-1]==0){ q2[tail].x=i; q2[tail++].y=m-1; }else{ idMap[a[i][m-1]]=true; } } for(int i=0;i<m;i++){ if(a[0][i]==0){//横向,最上面那一列都要检测 q2[tail].x=0; q2[tail++].y=i; }else{ idMap[a[0][i]]=true; } if(a[n-1][i]==0){ q2[tail].x=n-1; q2[tail++].y=i; }else{ idMap[a[n-1][i]]=true; } } //检测好之后基于上面的结果进行广搜 while(head!=tail){ for(int k=0;k<4;k++){ int tx=q2[head].x+dir[k][0]; int ty=q2[head].y+dir[k][1]; if(tx<0 ||tx>=n || ty<0 ||ty>=m ){ continue; }//然后就是根据这个外轮廓的零,去搜附近的非0,并且标记 if(a[tx][ty]==0 && book[tx][ty]==0 ){//避免搜到重复的零 book[tx][ty]=1; //入队 q2[tail].x=tx; q2[tail++].y=ty; } else if(a[tx][ty]!=0){ idMap[a[tx][ty]]=true; } } head++; } /* for(map<int,bool>::iterator iter=idMap.begin();iter!=idMap.end();iter++ ){ cout<<iter->first<<" "<<iter->second<<endl; } for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cout<<a[i][j]<<" "; } cout<<endl; } */ //外轮廓已经全部找出,接着就是把那些不是内轮廓的并到外轮廓中去. for(int i=2;i<color;i++){ if(idMap[i]==true){//如果此轮廓为外轮廓 continue; } //合并内轮廓 //首先是遍历邻接表找到内轮廓 int x=0,y=0; for(int j=0;j<(int)dataMap.size();j++){ x=dataMap[j][0].first; y=dataMap[j][0].second; if(a[x][y]==i){ //然后将这个区域内的点全部转化为外轮廓的点 for(int z=x;z<n;z++){ if(idMap[a[z][y]]==true){ int color_now=a[z][y]; //然后遍历邻接表,把对应的元素转化一下 for(int o=0;o<(int)dataMap[j].size();o++){ int tx=dataMap[j][o].first; int ty=dataMap[j][o].second; a[tx][ty]=color_now; } } } } } } map<int,int> numMap; int Max=-0x3f3f3f3f; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(a[i][j]!=0 && numMap[a[i][j]]==0){//初次出现 numMap[a[i][j]]=1; } //非首次出现 else if(a[i][j]!=0 && numMap[a[i][j]]!=0){ numMap[a[i][j]]++; } } } cout<<numMap.size()<<" "; for(map<int,int>::iterator iter=numMap.begin();iter!=numMap.end();iter++ ){ Max=std::max(iter->second,Max); } cout<<Max; return 0; }