下面是一个简单的代码(C++),使用简单的dfs来标记不同的组件,你可以尝试一下。
例如,如果您的标准输入输入是
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;
}