给一个二维数组,假设只有0,1标记,找出标记1可以连通的区域,这里只考虑上下左右四个方向。
从左到右,从上到下扫描二维数组,如果当前节点在地图中为1,那么影响它所属的连通区域标号的就只有上和左,这样就分为下面四种情况:
1、上和左在地图上都是1,并且连通区域标号不同,那就合并这两个区域,并将总的区域数减1,新的连通区域标号设置为上和左中最小的一个。如果相同,就直接设值,不用合并。
2、只有上为1,则直接设为上的区域标号。
3、只有左为1,则直接设为左的区域标号。
4、否则,新建一个区域标号。
#include<stdio.h> #include<string.h> //地图数组 int Map[100][100]; //标记数组 int flag[100][100]; //连通区域序号 int set[100]; //找到最小的连通区域标号 int find(int k) { int r = set[k]; while(r != set[r]) { r = set[r]; } return r; } //地图为m行n列,边界上加了一圈0,防止越界 int FindConnectArea(int m, int n) { if(m < 1 || n < 1) return 0; int count = 0; int t = 0; int i,j; int r1, r2; int Temp; for(i = 1; i <= m; ++i) { for(j = 1; j <= n; ++j) { if(Map[i][j]) { if(Map[i - 1][j] && Map[i][j - 1]) { //找该标记所属的连通区域 r1 = find(flag[i - 1][j]); r2 = find(flag[i][j - 1]); if(r1 == r2) { flag[i][j] = r1; } else//不同就合并,并把标记重置为较小的一个 { if(r1 > r2) { set[r1] = r2; flag[i][j] = r2; } else { set[r2] = r1; flag[i][j] = r1; } --count; } } else if(Map[i - 1][j]) flag[i][j] = find(flag[i - 1][j]); else if(Map[i][j - 1]) flag[i][j] = find(flag[i][j - 1]); else { //新建一个连通区域标记 flag[i][j] = ++t; ++count; } }//end if(Map[i][j]) }//end for i }//end for j return count; } //打印地图 void OutPut(int m, int n) { int i,j; for(i = 1; i <= m; ++i) { for(j = 1; j <= n; ++j) { if(Map[i][j]) printf("%d ",find(flag[i][j])); else printf("0 "); } printf("\n"); } } void main() { int m,n; int i,j; int Count; while(scanf("%d %d",&m,&n) != EOF) { memset(flag,0,sizeof(flag)); memset(Map,0,sizeof(flag)); for(i = 1; i <= m; ++i) for(j = 1; j <= n; ++j) scanf("%d",&Map[i][j]); for(i = 0; i < 100; ++i) set[i] = i; Count = FindConnectArea(m,n); printf("一共%d个连通区域\n",Count); OutPut(m,n); } }