蓝桥杯真题保姆级解析：用BFS数岛屿，从地图边界海水搜索讲起
蓝桥杯BFS实战：从海水搜索视角破解岛屿计数难题
当面对蓝桥杯算法竞赛中经典的"岛屿计数"问题时，大多数选手的第一反应是直接扫描地图寻找陆地并进行标记。但今天我要分享的是一种更为巧妙的思路——通过搜索海水来间接统计岛屿。这种方法不仅能高效解决问题，还能正确处理"岛屿套岛屿"等复杂边界情况，让我们一起来探索这个逆向思维的魅力。
1. 重新定义问题：为什么从海水入手？
在传统的岛屿计数解法中，我们通常会遍历整个矩阵，每当遇到未被访问的陆地（值为1的单元格）时，就启动一次BFS或DFS来标记所有相连的陆地，同时增加岛屿计数。这种方法虽然直观，但在处理某些特殊场景时会遇到困难。
考虑下面这个地图示例：
00000 01110 01010 01110 00000按照传统方法，我们会找到中心的陆地并标记为一个岛屿。但如果地图变成这样：
11111 10001 10101 10001 11111这个环形岛屿内部还包含一个小岛，传统方法可能会错误地将其识别为两个独立岛屿，而实际上它们应该被视为一个整体。
海水搜索法的核心优势：
- 天然处理封闭环形岛屿中的子岛屿
- 减少不必要的陆地遍历
- 更符合"被海水包围"的岛屿定义
- 自动排除与地图边界相连的"伪岛屿"
2. 海水搜索的算法框架
让我们构建一个完整的海水搜索解决方案。这个算法需要维护两个访问矩阵：一个记录已探索的海水区域，另一个记录已统计的陆地岛屿。
2.1 数据结构准备
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int N = 100; int grid[N][N]; // 存储地图数据 int n, m; // 地图尺寸 bool sea_visited[N][N]; // 海水访问标记 bool land_visited[N][N]; // 陆地访问标记 // 海水搜索的8个方向（包含对角线） int sea_dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0}; int sea_dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1}; // 陆地搜索的4个方向（仅上下左右） int land_dx[4] = {-1, 0, 1, 0}; int land_dy[4] = {0, 1, 0, -1};2.2 边界海水搜索策略
算法的核心是从地图边界上的海水单元格开始搜索：
void solve() { // 初始化 int island_count = 0; memset(sea_visited, false, sizeof(sea_visited)); memset(land_visited, false, sizeof(land_visited)); // 从边界海水开始搜索 for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if((i == 0 || i == n-1 || j == 0 || j == m-1) && !grid[i][j] && !sea_visited[i][j]) { bfs_sea(i, j); } } } // 处理全陆地地图的特殊情况 if(island_count == 0 && grid[0][0] == 1) { island_count = 1; } cout << island_count << endl; }3. 双重BFS的实现细节
海水搜索法的关键在于两种不同的BFS：一种用于探索海水区域，另一种用于标记相连的陆地。
3.1 海水BFS实现
void bfs_sea(int x, int y) { queue<pii> q; sea_visited[x][y] = true; q.push({x, y}); while(!q.empty()) { auto current = q.front(); q.pop(); for(int i = 0; i < 8; i++) { int nx = current.first + sea_dx[i]; int ny = current.second + sea_dy[i]; // 检查边界 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 遇到未访问的海水 if(!grid[nx][ny] && !sea_visited[nx][ny]) { sea_visited[nx][ny] = true; q.push({nx, ny}); } // 遇到未统计的陆地 else if(grid[nx][ny] && !land_visited[nx][ny]) { island_count++; bfs_land(nx, ny); } } } }3.2 陆地BFS实现
当海水搜索遇到陆地时，启动陆地BFS来标记整个岛屿：
void bfs_land(int x, int y) { queue<pii> q; land_visited[x][y] = true; q.push({x, y}); while(!q.empty()) { auto current = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int nx = current.first + land_dx[i]; int ny = current.second + land_dy[i]; // 检查边界 if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 遇到相连的未访问陆地 if(grid[nx][ny] && !land_visited[nx][ny]) { land_visited[nx][ny] = true; q.push({nx, ny}); } } } }4. 算法正确性分析与优化
4.1 为什么这种方法能正确处理子岛屿？
海水搜索法的巧妙之处在于它自然地遵循了岛屿的定义——被海水完全包围的陆地。当海水从边界向内渗透时：
- 任何与边界海水相连的陆地都不被视为岛屿（因为它们没有被完全包围）
- 只有被海水完全包围的陆地才会被统计
- 环形岛屿内部的陆地只有在外部海水无法到达时才会被统计
考虑这个复杂案例：
0000000 0111110 0101010 0111110 0000000传统方法会错误地统计两个岛屿，而海水搜索法会正确地识别为一个岛屿，因为内部的小岛被外部环形陆地完全包围。
4.2 性能优化技巧
虽然时间复杂度仍然是O(n×m)，但我们可以进行一些优化：
- 提前终止条件：当所有边界海水都被访问且没有发现新的陆地时，可以提前结束
- 并行搜索：使用多队列同时从多个边界点开始搜索
- 内存优化：对于大地图，可以使用位压缩来存储访问状态
// 优化后的边界搜索逻辑 bool has_ocean = false; for(int i = 0; i < n; i++) { if(!grid[i][0] && !sea_visited[i][0]) { bfs_sea(i, 0); has_ocean = true; } if(!grid[i][m-1] && !sea_visited[i][m-1]) { bfs_sea(i, m-1); has_ocean = true; } } for(int j = 0; j < m; j++) { if(!grid[0][j] && !sea_visited[0][j]) { bfs_sea(0, j); has_ocean = true; } if(!grid[n-1][j] && !sea_visited[n-1][j]) { bfs_sea(n-1, j); has_ocean = true; } }5. 常见错误与调试技巧
在实现海水搜索法时，有几个常见的陷阱需要注意：
方向向量错误：
- 海水搜索需要8方向（包含对角线）
- 陆地搜索只需要4方向（上下左右）
访问标记重置：
- 在处理多个测试用例时，忘记重置访问数组
- 解决方案：在每次solve()开始时清空数组
全陆地地图处理：
- 当地图全是陆地时，海水搜索可能不会统计任何岛屿
- 需要特殊处理：
if(island_count == 0 && grid[0][0] == 1)
边界条件检查：
- 确保所有数组访问都在边界内
- 可以在check函数中添加断言
bool check(int x, int y) { assert(x >= 0 && x < n && y >= 0 && y < m); return true; }6. 实战演练与变种问题
让我们通过一个完整案例来巩固这个算法：
输入地图：
5 5 11111 10001 10101 10001 11111执行过程：
- 检查边界点，发现全部是陆地，没有边界海水
- 由于island_count为0且grid[0][0]为1，判定为全陆地地图
- 输出岛屿数为1
变种问题思考：
- 如何统计湖泊数量（被陆地包围的水域）？
- 如何处理三维立体地图中的岛屿计数？
- 如果允许岛屿对角线连接，算法需要如何调整？
对于第一个变种，我们可以采用类似的思路，但改为从陆地边界开始搜索，记录被完全包围的水域。这再次证明了海水搜索法的通用性。
在实际编程竞赛中，理解算法的核心思想比死记硬背代码更重要。海水搜索法展示了如何通过改变视角来简化问题，这种思维方式在解决其他问题时也同样宝贵。