[C++]油田(Oil Deposits)-用DFS求连通块

时间:2022-04-15 05:06:04

[本博文非博主原创,均摘自:刘汝佳《算法竞赛入门经典》(第2版) 6.4 图]

[程序代码根据书中思路,非独立实现]

例题6-12 油田(Oil Deposits,UVa572)

  输入一个m行n列的字符矩阵,统计字符“@”组成多少个八连块。如果两个字符“@”所在的格子相邻(横、纵或者对角线方向),就说它们属于一个八连块。例如,下图中有两个八连块。

[C++]油田(Oil Deposits)-用DFS求连通块

一、分析

  1.1 整体思路

  图也有DFS和BFS遍历。由于DFS更容易编写,一般用DFS查找连通块:从每个"@"格子出发,递归遍历它周围的"@"格子。每次访问一个格子时,就给它写上一个"连通分量编号",这样就可以在访问之前检查它是否已经有了编号,从而避免同一个格子访问多次。

  1.2 各坐标的邻接位置(3X3)扫描器

[C++]油田(Oil Deposits)-用DFS求连通块

二、程序实现

//用DFS求连通块
#include<iostream>
#include<string.h>
using namespace std; const int maxn = ;
int cnt;
int *cntArray;
char matrix[maxn][maxn];
int idx[maxn][maxn];//标记数组
int m;
int n; void print(int rows, int cols){
for(int i=;i<rows;i++){
for(int j=;j<cols;j++){
printf("%d\t", idx[i][j]);
}
printf("\n");
}
} void dfs(int row,int col,int id){
if(row< || row>=m || col < || col >=n)
return;//边界
if((matrix[row][col] != '@') || (idx[row][col] > ))//已被标记或者不是@区域
return;
idx[row][col] = id;
for(int drow=-;drow<;drow++){//(邻接)扫描器
for(int dcol=-;dcol<;dcol++){
dfs(row + drow, col + dcol, id);
}
}
} int countIdx(){
cntArray = new int[cnt+];
memset(cntArray, , sizeof(cntArray));
int cursor = ;
for(int i=;i<m;i++){
for(int j=;j<n;j++){
cursor = matrix[i][j];
cntArray[cursor]++;
}
}
} int main(){
while(scanf("%d %d", &m, &n) == && m && n){
for(int i=;i<m;i++){
scanf("%s", matrix[i]);
}
memset(idx, , sizeof(idx));
int cnt = ;
for(int i=;i<m;i++){
for(int j=;j<n;j++){
if(idx[i][j] == && matrix[i][j] == '@')
dfs(i, j, ++cnt);
}
}
print(m, n);
}
return ;
}
/*
5 5
****@
*@@*@
*@**@
@@@*@
@@**@
*/

效果图:

[C++]油田(Oil Deposits)-用DFS求连通块

三、参考文献

  1.刘汝佳.算法竞赛入门经典