根据给定文件的信息，我们可以提炼出以下几个关键知识点：
### 一、题目背景及来源
- **题目名称**：“全球变暖”。
- **比赛名称**：2018年蓝桥杯软件类省赛（软件类）C/C++大学A组第8题。
- **来源**：此题目为蓝桥杯竞赛真题之一，旨在考察参赛者的算法设计能力及编程技巧。
- **提供者**：题目解析由倪文迪（华东理工大学计算机系软件192班）和罗勇军老师提供。
### 二、题目描述
题目要求解决的问题是：给定一张NxN像素的照片，其中“.”表示海洋，“#”表示陆地。相邻的陆地（即上下左右四个方向上连在一起的陆地）组成一座岛屿。由于全球变暖导致的海平面上升，预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说，如果一块陆地像素与海洋相邻（即上下左右四个相邻像素中有海洋），它就会被淹没。需要求出照片中有多少岛屿会被完全淹没。
### 三、解题思路
#### 1. 连通块问题
- **定义**：题目属于经典的连通块问题，即求解二维矩阵中相连的相同元素构成的连通区域数量。
- **解法**：可以通过深度优先搜索（DFS）或广度优先搜索（BFS）来遍历连通块。
#### 2. 题目分析
- **核心思想**：确定哪些岛屿会被完全淹没的关键在于判断该岛屿是否存在“高地”。若岛屿中有至少一个“高地”（即四周都被其他陆地包围的陆地像素），则该岛屿不会被完全淹没。
- **搜索策略**：遍历每个岛屿，统计没有“高地”的岛屿数量作为答案。
#### 3. 复杂度分析
- **时间复杂度**：对于每个像素点只需访问一次，故总时间复杂度为O(N^2)，其中N为矩阵的边长。
- **空间复杂度**：DFS和BFS的空间复杂度取决于最深路径长度或最长路径长度，均为O(N^2)。
### 四、代码实现
#### 1. DFS C++ 实现
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
char a[1010][1010]; //地图
int vis[1010][1010]={0}; //标记是否搜过
int d[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}}; //四个方向
int flag; //用于标记这个岛中是否被完全淹没
void dfs(int x, int y){
vis[x][y] = 1; //标记这个'#'被搜过
if(a[x][y+1]=='#' && a[x][y-1]=='#' && a[x+1][y]=='#' && a[x-1][y]=='#')
flag = 1; //上下左右都是陆地，不会淹没
for(int i = 0; i < 4; i++){
int nx = x + d[i][0], ny = y + d[i][1];
if(vis[nx][ny]==0 && a[nx][ny]=='#')
dfs(nx,ny);
}
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
cin >> a[i][j];
int ans = 0;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(a[i][j]=='#' && vis[i][j]==0){
flag = 0;
dfs(i,j);
if(flag == 0)
ans++;
}
cout << ans;
}
```
#### 2. BFS Python 实现
```python
from collections import deque
def bfs(x, y):
global grid, visited, n, ans
queue = deque([(x, y)])
visited[x][y] = True
has_high_ground = False
while queue:
x, y = queue.popleft()
if all(grid[x+dx][y+dy] == '#' for dx, dy in directions):
has_high_ground = True
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < n and 0 <= ny < n and not visited[nx][ny] and grid[nx][ny] == '#':
queue.append((nx, ny))
visited[nx][ny] = True
if not has_high_ground:
ans += 1
grid = []
visited = [[False] * 1010 for _ in range(1010)]
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
n = int(input())
for i in range(n):
grid.append(list(input()))
ans = 0
for i in range(n):
for j in range(n):
if grid[i][j] == '#' and not visited[i][j]:
bfs(i, j)
print(ans)
```
### 五、总结
本题通过考察连通块问题的解法，要求参赛者掌握基本的搜索算法如DFS和BFS，并能够灵活应用于实际问题中。通过对本题的分析和解答，不仅可以提升对算法的理解和应用能力，还能够培养解决实际问题的能力。
