下面是使用简单dfs标记不同组件的简单代码(C++),您可以试试。
例如,如果你的stdin的输入是
4 5
0 0 0 0 1
0 1 1 0 1
0 0 1 0 0
1 0 0 0 1
然后输出应该是
Graph:
0 0 0 0 1
0 1 1 0 1
0 0 1 0 0
1 0 0 0 1
Output:
0 0 0 0 1
0 2 2 0 1
0 0 2 0 0
3 0 0 0 4
相同数量的代表小区属于相同的分量。
我假设所有的8方向属于同一个组件,如果你只是想4方向, 变化DX []和dy []
而且我假设输入最多为200 * 200 ,我做了一些事情,以避免处理那些恼人的阵列外运问题,你可以检查出来:)
#include<cstdio>
#include<cstdlib>
#include<cstring>
int g[202][202] = {0};
int w[202][202] = {0};
int dx[8] = {-1,0,1,1,1,0,-1,-1};
int dy[8] = {1,1,1,0,-1,-1,-1,0};
void dfs(int x,int y,int c){
w[x][y] = c;
for(int i=0; i<8;i++){
int nx = x+dx[i], ny = y+dy[i];
if(g[nx][ny] && !w[nx][ny]) dfs(nx,ny,c);
}
}
int main(){
int row, col, set = 1;
scanf("%d%d", &row, &col);
for(int i=1; i<=row; i++) for(int j=1; j<=col; j++) scanf("%d", &g[i][j]);
for(int i=1; i<=row;i++)
for(int j=1; j<=col; j++)
if(g[i][j] && !w[i][j])
dfs(i,j,set++);
printf("Graph:\n");
for(int i=1; i<=row;i++){
for(int j=1; j<=col;j++)
printf("%d ", g[i][j]);
puts("");
}
puts("");
printf("Output:\n");
for(int i=1; i<=row;i++){
for(int j=1; j<=col;j++)
printf("%d ", w[i][j]);
puts("");
}
return 0;
}
双通道是好的。将所有标签全部贴上后,只需对它们进行迭代,然后按标签将它们添加到单独的列表中。本质上,使它三通:) – Geobits
查找[洪水填充算法](http://en.wikipedia.org/wiki/Flood_fill) –
我的想法是连接组件标签(CCL)是好的,@Geobits是对,一旦你得到了这些组件的标签,后处理不是一个问题(就复杂性而言)。 我在想的是,实际上CCL似乎有点过分了......是不是一个简单的DFS可以标记具有相同复杂性的所有组件? – shole