蓝桥杯真题保姆级解析：用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 pairint, 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) { queuepii 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) { queuepii 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变种问题思考如何统计湖泊数量被陆地包围的水域如何处理三维立体地图中的岛屿计数如果允许岛屿对角线连接算法需要如何调整对于第一个变种我们可以采用类似的思路但改为从陆地边界开始搜索记录被完全包围的水域。这再次证明了海水搜索法的通用性。在实际编程竞赛中理解算法的核心思想比死记硬背代码更重要。海水搜索法展示了如何通过改变视角来简化问题这种思维方式在解决其他问题时也同样宝贵。