今天真的好累，开完组会刷今天的题刷了一天。还有助教的事情没做完，还有一些其他的破事全都对在一堆了。今天的前两道题自己AC的，后面两道题看题解写的，最后一道题的思路就算想出来了，实现起来也不简单。。。。处在红温的边缘

101.孤岛的总面积（卡码网）

为了巩固广度优先的遍历方法，这道题目我用BFS写的，这道题的BFS依然是只能探索出某一点所在的小岛屿，因此思路很简单，从地图的边缘出发，将地图边缘的岛屿探索出来，顺便得到这些位于边缘的岛屿的面积，然后再统计出整幅地图的水域面积，用地图面积减去水域面积，再减去边缘岛屿的总面积，结果就是中间孤岛的面积。

#include<iostream>
#include<vector>
#include<queue>using namespace std;void bfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y, int &S);vector<vector<int>> dirs = {{0, 1},  //向右{0, -1}, //向左{-1, 0}, //向上{1, 0}   //向下
};int main(){int M, N;cin >> N >> M;  //N行M列vector<vector<int>> graph(N, vector<int> (M));  //整个地图vector<vector<bool>> visited(N, vector<bool> (M, false));  //已经探索过的陆地矩阵int count_0 = 0;for(int i = 0; i < N; i++){   //构造陆地和水构成的0-1矩阵for(int j = 0; j < M; j++){cin >> graph[i][j];if(graph[i][j] == 0) count_0++;}}/***********遍历地图边缘的岛屿***********/int S = 0; //边缘岛屿的总面积for(int i = 0; i < M - 1; i++){ //上边缘if(graph[0][i] == 1 && !visited[0][i]){//遇到新的岛屿bfs(graph, visited, 0, i, S);}}for(int i = 0; i < N - 1; i++){ //右边缘if(graph[i][M - 1] == 1 && !visited[i][M - 1]){//遇到新的岛屿bfs(graph, visited, i, M - 1, S);}}for(int i = M - 1; i > 0; i--){ //下边缘if(graph[N - 1][i] == 1 && !visited[N - 1][i]){//遇到新的岛屿bfs(graph, visited, N - 1, i, S);}}for(int i = N - 1; i > 0; i--){ //左边缘if(graph[i][0] == 1 && !visited[i][0]){//遇到新的岛屿bfs(graph, visited, i, 0, S);}}/***********遍历地图边缘的岛屿***********/cout << M * N - count_0 - S << endl;return 0;
}//广度优先搜索函数，调用该函数可以探索出（x，y）所在的整个岛屿
//在本题中，主要调用该函数来探索并计算边缘岛屿的面积
void bfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y, int &S){//输入参数为整个地图、已经探索过的陆地矩阵、当前位置的x、y坐标queue<pair<int, int>> My_Queue;My_Queue.push({x, y});visited[x][y] = true;S++;  //将当前位置计入总面积while(!My_Queue.empty()){pair<int, int> cur = My_Queue.front();My_Queue.pop();for(auto dir : dirs){int next_x = cur.first + dir[0];int next_y = cur.second + dir[1];if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size())continue;  //访问越界，直接跳过if(graph[next_x][next_y] == 1 && !visited[next_x][next_y]){//到达的地点为新的陆地My_Queue.push({next_x, next_y});visited[next_x][next_y] = true;S++;}}}}

102. 沉没孤岛（卡码网）

这道题和上一道题正好是反过来的，为了巩固深度优先遍历方法，这道题我就用的DFS来做，这道题我的想法是，遍历一圈地图边缘，同样将边缘的岛屿标记出来（visited[i][j] = true），然后再遍历整个地图，只有当走到边缘的岛屿上时才打印1，否则打印0（水域或者孤岛）。原理还是比较简单的。

#include<iostream>
#include<vector>using namespace std;void dfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y);vector<vector<int>> dirs = {{0, 1},  //向右{0, -1}, //向左{-1, 0}, //向上{1, 0}   //向下
};int main(){int M, N;cin >> N >> M;  //N行M列vector<vector<int>> graph(N, vector<int> (M));  //整个地图vector<vector<bool>> visited(N, vector<bool> (M, false));  //已经探索过的陆地矩阵int count_0 = 0;for(int i = 0; i < N; i++){   //构造陆地和水构成的0-1矩阵for(int j = 0; j < M; j++)cin >> graph[i][j];}/***********遍历地图边缘的岛屿***********/for(int i = 0; i < M - 1; i++){ //上边缘if(graph[0][i] == 1 && !visited[0][i]){//遇到新的岛屿dfs(graph, visited, 0, i);}}for(int i = 0; i < N - 1; i++){ //右边缘if(graph[i][M - 1] == 1 && !visited[i][M - 1]){//遇到新的岛屿dfs(graph, visited, i, M - 1);}}for(int i = M - 1; i > 0; i--){ //下边缘if(graph[N - 1][i] == 1 && !visited[N - 1][i]){//遇到新的岛屿dfs(graph, visited, N - 1, i);}}for(int i = N - 1; i > 0; i--){ //左边缘if(graph[i][0] == 1 && !visited[i][0]){//遇到新的岛屿dfs(graph, visited, i, 0);}}/***********遍历地图边缘的岛屿***********/for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){if(graph[i][j] == 1 && visited[i][j])cout << 1 << " ";else cout << 0 << " ";}cout << endl;}return 0;
}//深度优先递归函数，调用该函数可以探索出（x，y）所在的整个岛屿
//在本题中，主要调用该函数来探索并计算边缘岛屿的面积
void dfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y){//输入参数为整个地图、已经探索过的陆地矩阵、当前位置的x、y坐标visited[x][y] = true;for(auto dir : dirs){int next_x = x + dir[0];int next_y = y + dir[1];if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size())continue;  //访问越界，直接跳过if(graph[next_x][next_y] == 1 && !visited[next_x][next_y]){//到达新的陆地visited[next_x][next_y] = true;dfs(graph, visited, next_x, next_y);}}
}

103.水流问题（卡码网）

这道题我只想到了暴力遍历方式，肯定会超时。。直接看的题解，我觉得这道题的思路还是比较有意思的，第一边界的点向高处爬，通过BFS或者DFS统计出第一边界上的点所能到达的地点，那么反过来这些地点肯定能够流到第一边界，第二边界上的点也进行类似的操作，二者的交集就是既能到达第一边界又能到达第二边界的点，这种逆流而上的思路很妙啊！理解了思路以后代码很快就写出来了。

#include<iostream>
#include<vector>using namespace std;void dfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y);vector<vector<int>> dirs = {{0, 1},  //向右{0, -1}, //向左{-1, 0}, //向上{1, 0}   //向下
};int main(){int M, N;cin >> N >> M;  //N行M列vector<vector<int>> graph(N, vector<int> (M));  //整个地图vector<vector<bool>> visited_1(N, vector<bool> (M, false));  //从第一边界出发所能到达的地点矩阵vector<vector<bool>> visited_2(N, vector<bool> (M, false));  //从第二边界出发所能到达的地点矩阵for(int i = 0; i < N; i++){   //构造陆地和水构成的0-1矩阵for(int j = 0; j < M; j++)cin >> graph[i][j];}//遍历最左列和最右列for(int i = 0; i < N; i++){dfs(graph, visited_1, i, 0); //从最左列（第一边界）出发dfs(graph, visited_2, i, M - 1); //从最右列（第二边界）出发}//遍历最上行和最下行for(int i = 0; i < M; i++){dfs(graph, visited_1, 0, i); //从最上行（第一边界）出发dfs(graph, visited_2, N - 1, i); //从最下行（第二边界）出发}for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){if(visited_1[i][j] && visited_2[i][j])cout << i << " " << j << endl;}}return 0;
}//深度优先递归函数,调用该函数能得到从某个边界出发，所能达到的最高处
void dfs(const vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y){//输入参数为整个地图、已经探索过的陆地矩阵、当前位置的x、y坐标if(visited[x][y]) return ;  //防止重复访问（终止条件）visited[x][y] = true;for(auto dir : dirs){int next_x = x + dir[0];int next_y = y + dir[1];if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size())continue;  //访问越界，直接跳过if(graph[next_x][next_y] >= graph[x][y])//可以继续向上逆流dfs(graph, visited, next_x, next_y);}
}

104. 建造最大岛屿（卡码网）

这道题是今天最恶心的一道题目，没有之一。这道题的思路就是先探索出整个地图的岛屿，不同的岛屿用不同的标号区分，例如在地图中共存在3个岛屿，那么原来的地图矩阵从0-1矩阵赋值为包含0、2、3、4的矩阵，其中0依然表示水域，岛屿2上的点一律赋值为2，岛屿3上的点一律赋值为3，以此类推。这只是第一步，在划分完岛屿之后，就依次遍历地图中的水域点，计算当前水域点变为陆地后，与周围岛屿合并后的面积，在循环迭代中取最大值即可。
思路看上去很简单，但是说的容易做的难，中间实现需要引入大量变量，一不小心就会把自己弄得晕头转向，真的挺恶心的。
在第一阶段，在划分岛屿的过程中，需要使用一个哈希表统计各个岛屿的面积，键为岛屿标号，值为岛屿面积。
在第二阶段，每一次到新的水域点，都需要统计其四周是否存在岛屿，如果有岛屿要将岛屿的面积与当前岛屿面积相加，并且将统计过的岛屿加入一个集合，防止重复计算。注意，这里的集合中的已访问岛屿是相对于当前水域点而言的，当遍历到下一个水域点时，需要将集合清空，重新判断。
话不多说，献上我的屎山代码！

#include<iostream>
#include<vector>
#include <unordered_set>
#include <unordered_map>using namespace std;vector<vector<int>> dirs = {{0, 1},  //向右{0, -1}, //向左{-1, 0}, //向上{1, 0}   //向下
};
int island_s;   //统计岛屿面积void dfs(vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y, int mark);int main(){int M, N;cin >> N >> M;  //N行M列vector<vector<int>> graph(N, vector<int> (M));  //整个地图vector<vector<bool>> visited(N, vector<bool> (M, false));  //已经探索过的陆地矩阵for(int i = 0; i < N; i++){   //构造陆地和水构成的0-1矩阵for(int j = 0; j < M; j++)cin >> graph[i][j];}//开始给探索地图上的岛屿并给岛屿编号int mark = 2;   //岛屿编号unordered_map<int ,int> island;for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){if(graph[i][j] == 1 && !visited[i][j]){//遇到新的岛屿island_s = 0;  //小岛面积置0dfs(graph, visited, i, j, mark);island[mark] = island_s;mark++;}}}//开始添加陆地//注意，本题存在初始地图就全为陆地的情况，这种情况下找不到海洋，得不到正确的面积//因此必须设置一个标志位判断是否为全陆地int result = 0;  //记录最后结果unordered_set<int> visitedGrid; // 标记访问过的岛屿bool is_Allgrid = true; //默认为全陆地for(int i = 0; i < N; i++){for(int j = 0; j < M; j++){int island_count = 1;  //记录添加陆地后的岛屿数量visitedGrid.clear();   //将已访问列表清空if(graph[i][j] == 0){is_Allgrid = false;for(auto dir : dirs){int near_x = i + dir[0];int near_y = j + dir[1];if(near_x < 0 || near_x >= graph.size() || near_y < 0 || near_y >= graph[0].size())continue;  //访问越界，直接跳过if (visitedGrid.count(graph[near_x][near_y])) //返回1则说明已经访问过该岛屿continue; // 添加过的岛屿不要重复添加island_count += island[graph[near_x][near_y]];  //将周围的岛屿面积加入visitedGrid.insert(graph[near_x][near_y]);  //将当前的岛屿加入已访问列表中}}result = max(result, island_count);}}result = is_Allgrid ? M * N : result;cout << result << endl;return 0;
}//深度优先搜索递归函数
void dfs(vector<vector<int>> &graph, vector<vector<bool>> &visited, int x, int y, int mark){//输入参数为整个地图、已经探索过的陆地矩阵、当前位置的x、y坐标//终止条件if(visited[x][y]) return ;  //若已经探索过就直接退出visited[x][y] = true;island_s++;  //面积加一graph[x][y] = mark;for(auto dir : dirs){int next_x = x + dir[0];int next_y = y + dir[1];if(next_x < 0 || next_x >= graph.size() || next_y < 0 || next_y >= graph[0].size())continue;  //访问越界，直接跳过if(graph[next_x][next_y] == 1 && !visited[next_x][next_y]){dfs(graph, visited, next_x, next_y, mark);}}
}

真的好累，快点熬到训练结束的那一天吧┭┮﹏┭┮