预告：我用两年写的新书《算法竞赛》，已于2022年2月交给清华大学出版社，预计于2022年7月出版。《算法竞赛》是一本“大全”，内容覆盖“基础-中级-高级”，篇幅700页左右。部分知识点的草稿已经在本博客发表。本篇博客节选自新书《算法竞赛》的“3.1.6 连通性判断”。

2018年蓝桥杯省赛真题 全球变暖 https://www.lanqiao.cn/problems/178/learning/ 题目描述：有一张某海域 N×N 像素的照片，".“表示海洋、”#"表示陆地，如下图所示：

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有 2 座岛屿。 由于全球变暖导致海面上升，岛屿边缘一个像素的范围会被海水淹没。如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。例如上图中的海域未来会变成如下样子：

请计算：照片中有多少岛屿会被完全淹没。 输入：第一行包含一个整数N (1≤N≤1000)，以下N行N列代表一张海域照片。照片保证第 1 行、第 1 列、第N行、第N列的像素都是海洋。 输出：一个整数表示答案。

   这是基本的连通性问题，计算步骤是：遍历一个连通块（找到这个连通块中所有的’#‘，并标记已经搜过，不用再搜）；再遍历下一个连通块…；遍历完所有连通块，统计有多少个连通块。    连通性判断需要用暴力搜索解决：挨个搜连通块上的所有点，不遗漏一个；另外每个点只搜一次。这种简单的暴力搜索，用BFS和DFS都行，不仅很容易搜到所有点，而且每个点只搜一次，效率高。    回到本题，什么岛屿不会被完全淹没？若岛中有个陆地（称为高地），它周围都是陆地，那么这个岛不会被完全淹没。用DFS或BFS搜出有多少个岛（连通块），检查这个岛有没有高地，统计那些没有高地的岛（连通块）的数量，就是答案。    计算复杂度：因为每个像素点只用搜一次且必须至少搜一次，共 N 2 N^2 N2个点，复杂度 O ( N 2 ) O(N^2) O(N2)，不可能更好了。    为了对比DFS和BFS，下面先用DFS实现，后面再用BFS实现。   做题时，一般用DFS判断连通性，DFS比BFS编码少。

   DFS所有的像素点，若遇到’#‘，就继续DFS它周围的’#‘。把搜过的’#‘标记为已经搜过，不用再搜。统计那些没有高地的岛的数量，就是答案。    搜索时应该判断是不是出了边界。不过，题目已经说“照片保证第1行、第1列、第N行、第N列的像素都是海洋”，那么就不用判断边界了，到了边界，发现是水，DFS会自动停止搜索。    下面的代码，main()中每做一次DFS就是搜一个岛屿。代码中有两个重要变量。    （1）flag。在一次DFS中，如果发现这个岛有高地，置flag=1。如果这个岛中没有高地，那么有flag=0，统计答案ans++。    （2）vis[][]用于判断一个点是否被搜过。如果vis[][]==1，后面就不用重复搜了。代码第15行:

   判断vis[nx][ny]==0。如果没有这个判断，那么很多点会重复进行DFS，导致超时。这是一种剪枝技术，叫作“记忆化搜索”。