去年的蓝桥杯题,当时没想起来怎么判断连成环,直接寄。。
题目描述
小蓝得到了一副大小为 M×N
的格子地图,可以将其视作一个只包含字符 0(代表海水)和 1(代表陆地)的二维数组,地图之外可以视作全部是海水,每个岛屿由在上/下/左/右四个方向上相邻的 1 相连接而形成。
在岛屿 A
所占据的格子中,如果可以从中选出 k
个不同的格子,使得他们的坐标能够组成一个这样的排列:(x0,y0),(x1,y1),…,(xk−1,yk−1)
,其中 (x(i+1)%k,y(i+1)%k)
是由 (xi,yi)
通过上/下/左/右移动一次得来的 (0≤i≤k−1)
,此时这 k
个格子就构成了一个 “环”。
如果另一个岛屿 B
所占据的格子全部位于这个 “环” 内部,此时我们将岛屿 B
视作是岛屿 A
的子岛屿。
若 B
是 A
的子岛屿,C
又是 B
的子岛屿,那 C
也是 A
的子岛屿。
请问这个地图上共有多少个岛屿?
在进行统计时不需要统计子岛屿的数目。
样例
输入样例:
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
输出样例:
1
3
之前做过一个类似的题, 洛谷P1162 填涂颜色
区别是一个遍历四个方向,一个是遍历八个方向
所以我的思路是先从边上的0开始着手(边上极其相连接的0都是没被包围的,即不在环内的),用bfs搜,直至将所有的不在环内的0都打上标记,这个时候遍历一遍,没打标记的全部变成1,这个时候这个题就变成我们熟悉的题了——flood fill
只有0和1的图,判断有几个1的块
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 55;
int m,n;
int map[N][N];
bool use[N][N],hai[N][N];
int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
int dx2[4] = {-1, 0, 1, 0}, dy2[4] = {0, 1, 0, -1};
void bfs(int a,int b)
{
if (a < 1 || a > m || b < 1 || b > n || hai[a][b])
{
return;
}
hai[a][b]=true;
for(int i=0;i<8;i++)
{
int x=dx[i]+a,y=dy[i]+b;
if(x>=1&&x<=m&&y>=1&&y<=n&&map[x][y]==0&&!hai[x][y])
{
bfs(x,y);
}
}
return;
}
void bfs2(int a,int b)
{
if (a < 1 || a > m || b < 1 || b > n || use[a][b])
{
return;
}
use[a][b]=true;
for(int i=0;i<4;i++)
{
int x=dx2[i]+a,y=dy2[i]+b;
if(x>=1&&x<=m&&y>=1&&y<=n&&map[x][y]==1&&!use[x][y])
{
bfs2(x,y);
}
}
return;
}
int main()
{
int T;
cin>>T;
while(T--)
{
memset(use,false,sizeof use);
memset(hai,false,sizeof hai);
cin>>m>>n;
int ans=0;
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
scanf("%1d",&map[i][j]);
}
}
for (int i = 1;i <= n;i++)//搜素边上的0
{
if (map[1][i] == 0)
{
bfs(1, i);
}
if (map[m][i] == 0)
{
bfs(m, i);
}
}
for(int i=1;i<=m;i++)
{
if (map[i][1] == 0)
{
bfs(i, 1);
}
if (map[i][n] == 0)
{
bfs(i, n);
}
}
for(int i=1;i<=m;i++)
{
for(int j=1;j<=n;j++)
{
if(!hai[i][j])
{
map[i][j]=1;
}
}
}
for(int i=1;i<=m;i++)//洪水灌溉
{
for(int j=1;j<=n;j++)
{
if(map[i][j]==1&&!use[i][j])
{
bfs2(i,j);
ans++;
}
}
}
cout<<ans<<endl;
}
return 0;
}