其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海面上升，科学家预测未来几十年，岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样子：
请你计算：依照科学家的预测，照片中有多少岛屿会被完全淹没。
【输入格式】
第一行包含一个整数N。 (1 <= N <= 1000) 以下N行N列代表一张海域照片。照片保证第1行、第1列、第N行、第N列的像素都是海洋。
【输出格式】
一个整数表示答案。【样例输入】
7
【样例输出】
1 资源约定：峰值内存消耗（含虚拟机） < 256MCPU消耗 < 1000ms 请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。注意：
main函数需要返回0;只使用ANSI C/ANSI C++ 标准;不要调用依赖于编译环境或操作系统的特殊函数。所有依赖的函数必须明确地在源文件中 #include <xxx>不能通过工程设置而省略常用头文件。提交程序时，注意选择所期望的语言类型和编译器类型。
思路： 使用dfs分别计算出原始岛屿数和后来剩余的岛屿数即可。
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 10 using namespace std; 11 12 char mp[1010][1010]; 13 int grid[1010][1010]; // 用于涂色判断 14 int flag[1010][1010]; // mp[i][j]四周都不与海相邻，则flag[i][j] = 1 15 16 int N; 17 int dx[4] = { 1,-1,0,0 }; 18 int dy[4] = { 0,0,1,-1 }; 19 20 int color; // 第一块岛屿范围内涂1，第二块岛屿范围内涂2，以此类推 21 22 void dfs(int x, int y) 23 { 24 if (x < 0 || x >= N || y < 0 || y >= N) 25 return; 26 27 for (int i = 0; i < 4; ++i) 28 { 29 int xx = x + dx[i]; 30 int yy = y + dy[i]; 31 32 if (mp[xx][yy] == '#' && grid[xx][yy] == 0) 33 { 34 grid[xx][yy] = color; 35 dfs(xx, yy); 36 } 37 } 38 39 40 } 41 42 bool isNotAdjacent(int x, int y) // 该块陆地四周都不与海相邻，返回true 43 { 44 for (int i = 0; i < 4; ++i) 45 { 46 int xx = x + dx[i]; 47 int yy = y + dy[i]; 48 49 if (x >= 0 && x < N && y >= 0 && y < N && mp[xx][yy] == '.') 50 return false; 51 } 52 53 return true; 54 55 } 56 57 58 int main() 59 { 60 cin >> N; 61 for (int i = 0; i < N; ++i) 62 for (int j = 0; j < N; ++j) 63 { 64 cin >> mp[i][j]; 65 } 66 67 68 memset(grid, 0, sizeof(grid)); 69 color = 1; 70 // 使用dfs计算原始岛屿数 71 for (int i = 0; i < N; ++i) 72 for (int j = 0; j < N; ++j) 73 { 74 if (mp[i][j] == '#' && grid[i][j] == 0) // grid[i][j]等于0说明mp[i][j]还未被涂过色 75 { 76 dfs(i, j); 77 color++; 78 } 79 } 80 81 int start_num = color - 1; 82 83 memset(flag, 0, sizeof(flag)); 84 for (int i = 0; i < N; ++i) 85 for (int j = 0; j < N; ++j) 86 { 87 if (isNotAdjacent(i, j)) 88 { 89 flag[i][j] = 1; 90 } 91 } 92 93 94 for (int i = 0; i < N; ++i) 95 for (int j = 0; j < N; ++j) 96 { 97 if (flag[i][j] != 1) // 将所有被淹没的陆地置为 '.' 98 { 99 mp[i][j] = '.';100 }101 }102 103 104 105 memset(grid, 0, sizeof(grid));106 color = 1;107 // 再次使用dfs计算后来剩下的岛屿数108 for (int i = 0; i < N; ++i)109 for (int j = 0; j < N; ++j)110 {111 if (mp[i][j] == '#' && grid[i][j] == 0)112 {113 dfs(i, j);114 color++;115 }116 }117 118 int end_num = color - 1;119 120 cout << start_num - end_num << endl;121 122 return 0;123 }