题目描述
题意:
1. 能通过上下左右移动围绕成环的岛屿被称为环岛
2. 环岛内的岛屿被称为子岛,子岛不计数
3. 统计给出地图中的岛屿数量(不计算子岛)
解读:
1. 把环岛内部的海定义为内海,环岛外部的海定义为外海,外海可以连接各个环岛。
方法:
1. 我们用bfs搜索外海,一旦通过外海搜索到陆地,就对这个陆地dfs搜索标记,确定一个环岛位置,计数加1(也可以都用dfs或bfs搜索,用bfs快点)
2. 用bfs搜索外海时,我们需要一个起始搜索位置,这个位置必须是外海。为了防止起始位置不是外海,我们把地图的长和宽都扩展1,扩展部分都是外海,真正地图存在行(1,m),列(1,n),我们从(0,0)开始搜索,就可以保证一定从外海开始,就能搜索到所有的环岛
3. 对外海搜索,因为环岛是定义的四个方向上下左右,所以对于海而言,有上下左右斜八个方向可以被定义为外海,所以海的方向向量有八组。
注意事项
1. 状态数组初始化,因为我们扩展了地图,对状态数组初始化时要根据扩展的地图进项状态初始化
2.地图初始化:哇地图一定要初始化(因为地图没初始化debug了一小时),因为下一次给的地图可能比上一次小,无法覆盖上一次地图导致出错
代码部分
参考文献
https://www.bilibili.com/video/BV1uc411v7Tw/?spm_id_from=333.880.my_history.page.click
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int N = 52;
int m, n;
char cg[N][N];//输入时以字符串输入,再转为数字存入g数组
int g[N][N];//存一波地图
int st_road[N][N];
int st_sea[N][N];
int dx_road[4] = { -1,0,1,0 }; int dx_sea[8] = { -1,0,1,0,1,1,-1,-1 };
int dy_road[4] = { 0,1,0,-1 }; int dy_sea[8] = { 0,1,0,-1,1,-1,1,-1 };
int cnt;
typedef pair<int, int> PII;
queue<PII>q;
void dfs_road(int x, int y)
{
st_road[x][y] = 1;
for (int i = 0; i < 4; i++)
{
int a = x + dx_road[i]; int b = y + dy_road[i];
if (a<1 || a>m || b<1 || b>n) continue;//超界继续
if (st_road[a][b] == 1) continue;//走过继续
if (g[a][b] == 0) continue;//是海继续
st_road[a][b] = 1;
dfs_road(a, b);
}
}
void bfs_sea(int x, int y)
{
q.push({ x,y });
st_sea[x][y] = 1;//走过
while (q.size())
{
PII u = q.front();
q.pop();
for (int i = 0; i < 8; i++)
{
int a = u.first; int b = u.second;
a += dx_sea[i]; b += dy_sea[i];
if (a<0 || a>m + 1 || b<0 || b>n + 1) continue;//超出地图,直接下一格
if (g[a][b] == 0)//是海
{
if (st_sea[a][b] == 1) continue;//走过,找下一格
else//没有走过,入队
{
st_sea[a][b] = 1;//走过
q.push({ a,b });
}
}
if (g[a][b] == 1)//是陆地
{
if (st_road[a][b] == 1) continue;//走过,找下一格
else //没走过,进陆地的dfs吧这个地搜索,并外岛+1
{
cnt++;
dfs_road(a, b);
}
}
}
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
cnt = 0;
memset(g, 0, sizeof(g));//每次都要把地图初始化,防止下一次是小地图覆盖不了上一次的大地图
scanf("%d%d", &m, &n);
for (int i = 0; i <= m + 1; i++)//因为扩大了地图,所以要从0到m+1,0到n+1初始化
{
for (int j = 0; j <= n + 1; j++)
{
st_road[i][j] = 0; st_sea[i][j] = 0;
}
}
for (int i = 1; i <= m; i++)//村地图
{
scanf("%s", cg[i] + 1);//从1开始存
for (int j = 1; j <= n; j++)
{
g[i][j] = cg[i][j] - '0';
}
}
bfs_sea(0, 0);
printf("%d\n", cnt);
}
return 0;
}