[算法提高] DFS 深度优先搜索 数岛屿连通块面积
[问题背景]
假设'#'是陆地，'.'是海洋。
我们从图中把左、上、右、下四个方向相邻的'#'连起来作为一个连通块，也就是一个“岛屿”，每个岛屿的面积就是'#'的个数。
如图：
图中有三个连通块，按自左向右再自上而下的顺序，三个连通块的面积依次是4、2、1.
输出这些连通块的面积。
[测试样例1]
##.#.
#..#.
#...#
[输出样例1]
4 2 1
[测试样例2]
##.#..
#..#..
#...#.
###...
#....#
[输出样例2]
8 2 1 1
[测试样例3]
###..#
#.#...
###...
......
###.##
#.#.#.
[输出样例3]
8 1 5 3
[思路分析]
以左边的连通块为例，应能实现这样的递归访问，每次递归时都将面积+1
我们对二维数组中的元素进行遍历循环，遇到#就开始深搜，搜完一整个连通块后返回整个大循环，继续遍历后面的元素。
[代码求解]
以下是针对测试样例3编写的代码。
#define N 6
#define M 6
#include <iostream>
#include <vector>
using namespace std;
void dfs(int, int); // 声明深搜dfs函数
// 在main()之外声明的都是全局变量，main()后面的函数也可以使用这些全局变量
char c[N][M]; // 记录#.图
vector<int>area; // 记录各个连通块的面积
int sum = 0; // 置面积初值为0
int vis[N][M] = {0}; //记录每个元素是否被访问过，初值0表示没有访问过
int main(){
//int N, M; //N行M列
//cin >> N >> M;
//因为传长度为变量的二维数组给函数的问题本人还没有解决，所以很抱歉只能用宏定义的方法做
//记录#.图
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> c[i][j];
}
}
//遍历#.图中的元素
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
//如果这个元素[没有被访问过 && 是'#'] 那么对它深搜
if (vis[i][j] == 0 && c[i][j] == '#') dfs(i,j);
// 如果这个元素对应的连通块面积不是0，那么记入area中
// 对于. 这个元素也会生成为0的sum
if (sum!= 0) area.push_back(sum);
sum = 0; // 重置sum
}
}
//迭代器遍历area，输出结果
for (auto it = area.begin(); it != area.end(); it++){
cout << *(it) << " ";
}
return 0;
}
void dfs(int i, int j){
//深搜到达c[i][j]时标记其已被访问
vis[i][j] = 1;
//深搜到达新的'#'时面积加1
sum++;
//以下两行注释代码是输出样例中不需要的，它们只是帮你调试程序看过程变化用
//cout << "i=" << i << "j=" << j << endl;
//cout << "sum=" << sum << endl << endl;
//left
//向左，不能碰到边界，应该是没有被访问过的，应该是"#"号
if(j > 0 && vis[i][j-1] == 0 && c[i][j-1] == '#'){
dfs(i, j-1);
//递进到c[i][j-1]进行深搜
}
//up
//以下照此类推，注意各个下标不要写错
if(i > 0 && vis[i-1][j] == 0 && c[i-1][j] == '#'){
dfs(i-1, j);
}
//right
if(j < N-1 && vis[i][j+1] == 0 && c[i][j+1] == '#'){
dfs(i, j+1);
}
//down
if(i < N-1 && vis[i+1][j] == 0 && c[i+1][j] == '#'){
dfs(i+1, j);
}else{
return; //返回，对某个元素展开的深搜结束
}
}输出结果：
8 1 5 3 代码简洁版：
#define N 6
#define M 6
#include <iostream>
#include <vector>
using namespace std;
void dfs(int, int);
char c[N][M];
vector<int>area;
int sum = 0;
int vis[N][M] = {0};
int main(){
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> c[i][j];
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
if (vis[i][j] == 0 && c[i][j] == '#') dfs(i,j);
if (sum!= 0) area.push_back(sum);
sum = 0;
}
}
for (auto it = area.begin(); it != area.end(); it++){
cout << *(it) << " ";
}
return 0;
}
void dfs(int i, int j){
vis[i][j] = 1;
sum++;
if(j > 0 && vis[i][j-1] == 0 && c[i][j-1] == '#'){
dfs(i, j-1);
}
if(i > 0 && vis[i-1][j] == 0 && c[i-1][j] == '#'){
dfs(i-1, j);
}
if(j < N-1 && vis[i][j+1] == 0 && c[i][j+1] == '#'){
dfs(i, j+1);
}
if(i < N-1 && vis[i+1][j] == 0 && c[i+1][j] == '#'){
dfs(i+1, j);
}else{
return;
}
}很抱歉因为我个人的水平原因暂没有能写出由用户指定N行M列的代码，以后解决了会在这里补充，也希望得到高手的批评指正，非常感谢！
[方法总结]
深搜一般要通过递归实现，本题的深搜思路大致是：
1.遍历图中的每个元素
2.对未访问过的目标元素进行深搜
3.深搜时注意考虑图的边界和历史访问性的记录
4.对深搜产生的目标数据的处理
最值得注意的两点是：
1.图的边界
2.元素是否被访问过，这一信息的记录和处理
[拓展提高]
我认为人不应该仅仅满足于闭门造轮，也要出门看一看别人造的轮子是不是更好更快更漂亮。
所以我学习了这位博主的文章，虽然代码行数差不多：
小白成长日记（15）--岛屿面积问题（算法设计--dfs深度优先搜索） - rangkuimei0880的博客 - ****博客 https://blog.****.net/rangkuimei0880/article/details/78609941
[测试样例]
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
[输出样例]
9 5 38 3[代码拓展]
#define N 10
#define M 10
#include <iostream>
#include <vector>
using namespace std;
int dfs(int, int);
int c[N][M];
vector<int>area;
int vis[N][M] = {0};
int main(){
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> c[i][j];
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
if (vis[i][j] == 0 && c[i][j] != 0) {
int temp = dfs(i,j);
if(temp!=0) area.push_back(temp);
}
}
}
for (auto it = area.begin(); it != area.end(); it++){
cout << *(it) << " ";
}
return 0;
}
int dfs(int i, int j){
int sum = 0;
if (j >= 0 && i >= 0 && j < N && i < N) { //注意这里的=号能否取到
if (vis[i][j] == 0 && c[i][j] != 0 ) {
vis[i][j] = 1;
sum = 1;
sum += dfs(i,j-1);
sum += dfs(i-1,j);
sum += dfs(i,j+1);
sum += dfs(i+1,j);
}
return sum;
}else{
return 0;
}
}也是一种可行的解法。将dfs定义为int更为直接，返回值就是答案。
将dfs定义为void ，则需要更多地考虑全局变量的操作，但也能适应多任务场景，比如不但要数面积，还要统计岛屿数量和形状等。
我想了一下，开大数组可以由用户指定N和M，不过总归还不是那么完美，毕竟大数组也有个上限，就贴在这里吧。
#define MaxN 1000
#define MaxM 1000
#include <iostream>
#include <vector>
using namespace std;
void dfs(int, int, int, int);
char c[MaxN][MaxM];
vector<int>area;
int sum = 0;
int vis[MaxN][MaxM] = {0};
int main(){
int N, M;
cin >> N >> M;
for(int i = 0; i < N; i++){
for(int j = 0; j < M; j++){
cin >> c[i][j];
}
}
for (int i = 0; i < N; i++){
for (int j = 0; j < M; j++){
if (vis[i][j] == 0 && c[i][j] == '#') dfs(i,j,N,M);
if (sum!= 0) area.push_back(sum);
sum = 0;
}
}
for (auto it = area.begin(); it != area.end(); it++){
cout << *(it) << " ";
}
return 0;
}
void dfs(int i, int j, int N, int M){
vis[i][j] = 1;
sum++;
if(j > 0 && vis[i][j-1] == 0 && c[i][j-1] == '#'){
dfs(i, j-1, N, M);
}
if(i > 0 && vis[i-1][j] == 0 && c[i-1][j] == '#'){
dfs(i-1, j, N, M);
}
if(j < N-1 && vis[i][j+1] == 0 && c[i][j+1] == '#'){
dfs(i, j+1, N, M);
}
if(i < N-1 && vis[i+1][j] == 0 && c[i+1][j] == '#'){
dfs(i+1, j, N, M);
}else{
return;
}
}