題目

解析

這道題的思路就是遍歷所有島嶼，判斷每一塊陸地是否會沉沒。對于這種圖的遍歷，我們首先應該想到DFS。

代碼的注意思想就是，在主函數中遍歷找出所有島嶼，將其用DFS遍歷判斷其所有陸地。

注意一下代碼中的細節：
【
1.主函數每次給dfs傳島嶼時，需要初始化t（記錄島嶼是否會沉沒）
2.每次用完一個島嶼，將其重新命為其他符號，做標記（DFS核心）
】

講下DFS

深度優先搜索（DFS）是一種用于遍歷或搜索樹、圖或網格結構的算法，其核心思想是“盡可能深地探索分支，直到盡頭再回溯”。

適合使用DFS的場景：
1.連通區域遍歷
問題類型：需要找到所有相連的區域（如島嶼、迷宮中的連通路徑）。
示例：統計地圖中的島嶼數量、標記病毒感染的區域。

2.路徑問題
問題類型：尋找從起點到終點的所有可能路徑（如迷宮、棋盤游戲）。
示例：判斷迷宮是否有出口，計算八皇后問題的解法。

3.狀態空間搜索
問題類型：需要窮舉所有可能狀態的問題（如排列組合、子集生成）。
示例：生成所有可能的括號組合、排列數字。

總結
使用DFS的時機：需要遍歷所有可能路徑、處理連通區域、或狀態空間搜索時。

代碼

#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits>  // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n, book[1010][1010], cnt, t, ans, sum;
char map[1010][1010];int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};void dfs(int x, int y) {if (!t) {cnt = 0;//判斷該點【陸地】是否會被淹沒用t標記for (int i = 0; i < 4; i++) {if (map[x + dx[i]][y + dy[i]] != '.')cnt++;if (cnt == 4) {ans += 1;t = 1;}}}map[x][y] = '*';//標記用過的點//開始遍歷島嶼上的其他點【陸地】for (int i = 0; i < 4; i++) {int nx = x + dx[i], ny = y + dy[i];//越界or不是陸地就跳出if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] != '#')continue;//繼續判斷該島嶼的其他陸地dfs(nx, ny);}
}int main() {cin >> n;for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)cin >> map[i][j];for (int i = 1; i < n - 1; i++) {for (int j = 1; j < n - 1; j++) {if (map[i][j] == '#') { //找到島嶼，調用dfs遍歷島嶼中的所有陸地sum++;t = 0;//用于標記該島嶼是否會沉dfs(i, j);}}}cout << sum - ans << endl;//總島嶼數 - 不會沉沒的島嶼數return 0;
}