题目 3153: 蓝桥杯2023年第十四届省赛真题-岛屿个数题解

小蓝得到了一副大小为 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 的子岛屿。

请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：

01111

11001

10201

10001

11111

岛屿 2 在岛屿 1 的 “环” 内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。

对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：

111111

100001

020301

100001

111111

注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有“环”。

对于 30% 的评测用例，1 ≤ M, N ≤ 10。

对于 100% 的评测用例，1 ≤ T ≤ 10，1 ≤ M, N ≤ 50。

1.首先我们用一个比地图大一圈的矩阵来存储这个地图（只需要大一圈就行，题目50,50你就开52,52）

2.由于地图外都是海水，所以先所有点都初始化为0

3.然后，我们从(0,0)开始把所有相连的海水都标记为2，这个过程之后图中所有剩下没有被更改的0一定在岛屿内部（要八连通）

4.接下来我们再遍历一遍地图，把所有0都变成1，这样岛屿和其内部的子岛屿就“合为一体”了

5.接下来就是着色问题，每遇到一个四连通的的岛将其所有1都变成2，并且岛的个数加一，全部点遍历一遍得到答案

ac代码如下：

#pragma GCC optimize(3)
#include 
using namespace std;
#define endl '\n'
int m, n;
int nex[8][2] = { { -1, 0 }, { -1, 1 }, { 0, 1 }, { 1, 1 }, { 1, 0 }, { 1, -1 }, { 0, -1 }, { -1, -1 } }; // 八连通
char sea[52][52]; // 至少52x52
void dfs1(int x, int y) { 
	sea[x][y] = '2';                         
	int newx, newy;
	for (int i = 0; i = 0 && newx = 0 && newy = 1 && newx = 1 && newy > m >> n;
    for (int i = 0; i