当前位置：首页 > news >正文

搜索系列·连通块问题

news 2026/4/25 18:06:58

小引：

连通块问题是搜索问题下的一个分支，而搜索又是基于递归的，所以连通块问题也是基于递归的一类问题。

特点：

这一类问题的函数结构大多相同，在母模版上的修改不用太多。

经典例题：

最大黑区域，岛屿数量，最大岛屿，瓷砖，细胞数量......

例题模版：

输入n，m，并输入n行m列的矩阵，类型为int（或char）。求出在矩阵中上下左右（或加上左上，左下，右上，右下）连通起来的数字（或字符）数量。

解题步骤：

壹.定义变量：

代码范例如下：

其中，s代表连通块的数量。

贰.寻找合适的条件深搜：

代码范例如下：

#include<bits/stdc++.h>
using namespace std;
int a[数据最大至+5][数据最大至+5];
int n,m,s;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(a[i][j]==合适的条件)
{
s++;
dfs(i,j);
}
}
}
return 0;
}

例题：

问题描述

在一个 w×h 的矩形广场上，每一块 1×1 的地面都铺设了红色或黑色的瓷砖。小林同学站在某一块黑色的瓷砖上，他可以从此处出发，移动到上、下、左、右四个相邻的且是黑色的瓷砖上。现在，他想知道，通过重复上述移动所能经过的黑色瓷砖数。

输入要求：

第 1 行为 h、w（2≤w、h≤50），之间由一个空格隔开。以下为一个 w 行 h 列的二维字符矩阵，每个字符为“.”“#”“@”，

分别表示该位置为黑色的瓷砖、红色的瓷砖、小林的初始位置。

输出要求：

输出一行一个整数，表示小林从初始位置出发经过的黑色瓷砖数。

在这道题目的实现代码中，if判断语句中填写‘@’。

然后，我们要按照递归的四要素：类型，参数，边界，内容来完成我们的代码）

参.程序代码的完成：

边界：

void dfs(int x,int y)
{
if(x<1||x>n||y<1||y>m||a[x][y]==障碍)
{
return ;
}
}

因为我们要到不越界，无障碍的地方去，所以判断条件为：不越行，不越列，不到障碍上

代码范例如下：

#include<bits/stdc++.h>
using namespace std;
int h,w,s;char a[55][55];
void dfs(int x,int y)
{
if(x<1||x>w||y<1||y>h||a[x][y]=='#')
{
return ;
}
}
int main()
{
int i,j;
cin>>h>>w;int c,d;
for( i=1;i<=w;i++)
{
for( j=1;j<=h;j++)
{
cin>>a[i][j];
}
}
for(i=1;i<=w;i++)
{
for(j=1;j<=h;j++)
{
if(a[i][j]=='@')
{

c=i;d=j;

}
}
}
dfs(c,d);
cout<<s;
return 0;
}

内容：

标记：

标记有两种方法：

1.例：a[x][y]=障碍

2.例：flag[x][y]=1

代码范例如下：

#include<bits/stdc++.h>
using namespace std;
int h,w,s;char a[55][55];
void dfs(int x,int y)
{
if(x<1||x>w||y<1||y>h||a[x][y]=='#')
{
return ;
}
s++;
a[x][y]='#';
}
int main()
{
int i,j;
cin>>h>>w;int c,d;
for( i=1;i<=w;i++)
{
for( j=1;j<=h;j++)
{
cin>>a[i][j];
}
}
for(i=1;i<=w;i++)
{
for(j=1;j<=h;j++)
{
if(a[i][j]=='@')
{

c=i;d=j;

}
}
}
dfs(c,d);
cout<<s;
return 0;
}

方向拓展：

方法1：

dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
dfs(x-1,y-1);
dfs(x-1,y+1);
dfs(x+1,y-1);
dfs(x+1,y+1);

方法2：

int X[9]={1,-1,0,0,1,1,-1,-1},Y[9]={0,0,1,-1,1,-1,1,-1};

for(int i=1;i<8;i++)

{

dfs(x+X[i],y+Y[i]);

}

整体代码如下：

#include<bits/stdc++.h>
using namespace std;
int h,w,s;char a[55][55];
void dfs(int x,int y)
{
if(x<1||x>w||y<1||y>h||a[x][y]=='#')
{
return ;
}
s++;
a[x][y]='#';
dfs(x-1,y);
dfs(x+1,y);
dfs(x,y-1);
dfs(x,y+1);
}
int main()
{
int i,j;
cin>>h>>w;int c,d;
for( i=1;i<=w;i++)
{
for( j=1;j<=h;j++)
{
cin>>a[i][j];
}
}
for(i=1;i<=w;i++)
{
for(j=1;j<=h;j++)
{
if(a[i][j]=='@')
{

c=i;d=j;

}
}
}
dfs(c,d);
cout<<s;
return 0;
}