任务日期：7.27
题目一链接：101. 孤岛的总面积 (kamacoder.com)
思路：用bfs把边缘的陆地及其周边的陆地都变成海洋，并做上标记，然后继续用bfs把未标记的陆地的数量加起来。
代码：
#include <bits/stdc++.h>
using namespace std;
//思路：把靠边的陆地及其周边的陆地都变成海洋，然后以圈的形式遍历grid把陆地的数量并加起来
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
int bfs(vector<vector<int>> &grid,vector<vector<bool>> &visited,int x,int y) {grid[x][y] = 0;//处理当前点int count = 1;//每次bfsstd::queue<pair<int,int>> que;//存入当前节点四周未标记的陆地的位置que.push({x,y});while(!que.empty()) {//遍历所有符合标准的节点pair<int,int> cur = que.front();//当前点坐标que.pop();//弹出当前节点，防止重复遍历for(int i = 0;i < 4;i ++) {//遍历当前节点四周的的节点int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if(nextx < 0 || nextx == grid.size() || nexty < 0 || nexty == grid[0].size()) continue;if(grid[nextx][nexty] == 1) {grid[nextx][nexty] = 0;//此处既可以将陆地标记成海洋，又可以防止count多加count ++;que.push({nextx,nexty});//为下一圈遍历做准备}}}return count;
}
int main() {int n,m;cin>>n>>m;std::vector<vector<int>> grid(n + 1,vector<int> (m + 1,0));for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {cin>>grid[i][j];}}std::vector<vector<bool>> visited(n + 1,vector<bool> (m + 1,0));//左边和右边for(int i = 0;i < n;i ++) {if(grid[i][0] == 1) bfs(grid,visited,i,0);if(grid[i][m - 1] == 1) bfs(grid,visited,i,m - 1);}//上边和下边for(int i = 0;i < m;i ++) {if(grid[0][i] == 1) bfs(grid,visited,0,i);if(grid[n - 1][i] == 1) bfs(grid,visited,n - 1,i);}//遍历grid其他的点int result = 0;for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {if(grid[i][j] == 1) {result += bfs(grid,visited,i,j);//把每次bfs算的count都加在一起}}}cout<<result;return 0;
}难点：1.本题做标记不用再申请空间创建visited[][],而是直接将grid的值由1变成0，以此做上标记。
2.bfs需要构建队列，以此遍历外圈的点。
解释细节1：巧妙改变grid[][]的值，从而节省visited[][]空间
题目二链接：102. 沉没孤岛 (kamacoder.com)
思路：用bfs将边缘的陆地由1变为2，然后再用一个双层for循环把数值为1的陆地变成0，把2换成1即可
代码：
#include <bits/stdc++.h>
//思路：用bfs将边缘的陆地由1变为2，然后再用一个双层for循环把数值为1的陆地变成0，把2换成1即可
using namespace std;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};void bfs(vector<vector<int>> &grid,int x,int y) {std::queue<pair<int,int>> que;que.push({x,y});while(!que.empty()) {pair<int,int> cur = que.front();que.pop();for(int i = 0;i < 4;i ++) {int nextx = cur.first + dir[i][0];int nexty = cur.second + dir[i][1];if(nextx < 0 || nextx == grid.size() || nexty < 0 || nexty == grid[0].size()) continue;if(grid[nextx][nexty] == 1) {//隐藏了递归终止条件那一步grid[nextx][nexty] = 2;que.push({nextx,nexty});}}}
}int main() {int n,m;cin>>n>>m;std::vector<vector<int>> grid(n + 1,vector<int> (m + 1,0)) ;for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {cin>>grid[i][j];}}//找边上且未标记的陆地，并把标记他周围为标记的陆地：将1变成2实现标记，而不用重新开辟空间for(int i = 0;i < n;i ++) {if(grid[i][0] == 1) {grid[i][0] = 2;bfs(grid,i,0);//把周围的陆地也变成2}if(grid[i][m - 1] == 1) {grid[i][m - 1] = 2;bfs(grid,i,m - 1);//把周围的陆地也变成2}}for(int i = 0;i < m;i ++) {if(grid[0][i] == 1) {grid[0][i] = 2;bfs(grid,0,i);//把周围的陆地也变成2}if(grid[n - 1][i] == 1) {grid[n - 1][i] = 2;bfs(grid,n - 1,i);}}//把2在变成1,同时把1变成0for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {if(grid[i][j] == 1) grid[i][j] = 0;if(grid[i][j] == 2) grid[i][j] = 1;}}//最后输出gridfor(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {if(j != m - 1) cout<<grid[i][j]<<" ";else cout<<grid[i][j]<<endl;}}return 0;
}难点：1.本题做标记的方法是将边缘的陆地从1改成2（而不是利用visited进行标记），然后巧妙地利用一个双层for循环直接将孤岛改为海水，最后输出。
2.二维数组的指定形式输出
3.bfs需要构建队列，以此遍历外圈的点。
解释细节1：不用创建visited,节约了很大空间
题目三链接：103. 水流问题 (kamacoder.com)
思路：分别从第一组边界和第二组边界向中间逆流而上，最后返回两个边界都能到达的点。
代码：
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
//因为dfs里面我们只需要判断某个点是否被标记而不在乎被标记几次，所以一个visited就足够了
void dfs(vector<vector<int>> &grid,vector<vector<bool>> &visited,int x,int y) {//确定递归终止条件// if(visited[x][y]) return;//此时当前点四个方向的递归终止，这样可以避免进行重复相同操作。//确定当前层递归逻辑visited[x][y] = true;//注意它和递归终止条件之间的顺序关系for(int i = 0;i < 4;i ++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx == grid.size() || nexty < 0 || nexty == grid[0].size()) continue;//终止当前方向的递归if(grid[x][y] > grid[nextx][nexty] || visited[nextx][nexty]) continue;//结束当前方向的递归//可以沿当前方向递归dfs(grid,visited,nextx,nexty);}
}int main() {int n,m;cin>>n>>m;std::vector<vector<int>> grid(n + 1,vector<int> (m + 1,0));for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {cin>>grid[i][j];}}vector<vector<bool>> firsttborder(n + 1,vector<bool> (m + 1,false));vector<vector<bool>> secondborder(n + 1,vector<bool> (m + 1,false));//从左右两侧边界向中间逆流而上for(int i = 0;i < n;i ++) {dfs(grid,firsttborder,i,0);//最左侧第一组边界逆流而右dfs(grid,secondborder,i,m - 1);//最右侧第二组边界逆流而左}//从上下两个边界向中间逆流而上for(int i = 0;i < m;i ++) {dfs(grid,firsttborder,0,i);//最上侧第一组边界逆流而下dfs(grid,secondborder,n - 1,i);//最右侧第二组边界逆流而上}//输出每个符合条件的坐标for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {if(firsttborder[i][j] && secondborder[i][j]) cout<<i<<" "<<j<<endl;}}return 0;
}难点：
1.思路比较新颖：从原来的顺流而下改成从边界逆流而上解决问题。
2.递归终止条件有两个：一个是下一个节点的之更大；另一个是下一个节点没有被访问过。只有两个条件都满足时才能向下一个节点递归
3.子函数中可以改变由主函数传来的值并且不用返回就能得到新值，前提必须加地址符
题目四链接：104. 建造最大岛屿 (kamacoder.com)
思路：先利用dfs计算每个岛屿的面积，并且将面积和对应的编号存到哈希表gridnum中；然后遍历grid，当grid是0时，就将海变成陆地并且把四周的岛屿面积加起来最后取最大值。
代码：
#include <bits/stdc++.h>
using namespace std;
int dir[4][2] = {0,1,1,0,0,-1,-1,0};
//dfs计算每一块岛屿的面积
int dfs(vector<vector<int>> &grid,int x,int y,int mark,int &count) {//count在当前函数里要改变所以要加地址符grid[x][y] = mark;count ++;for(int i = 0;i < 4;i ++) {int nextx = x + dir[i][0];int nexty = y + dir[i][1];if(nextx < 0 || nextx == grid.size() || nexty < 0 || nexty == grid[0].size()) continue;if(grid[nextx][nexty] == 0 || grid[nextx][nexty] == mark) continue;//递归终止条件都集中到这里dfs(grid,nextx,nexty,mark,count);}return count;
}int main() {int n,m,count;cin>>n>>m;std::vector<vector<int>> grid(n + 1,vector<int> (m + 1,0));for(int i = 0;i < n;i ++) {for(int j = 0;j < m; j ++) {cin>>grid[i][j];}}//先结算孤岛的面积，并储存到哈希表map里,key代表编号，value代表大小unordered_map<int,int> gridnum;int mark = 2;bool allland = true;for(int i = 0;i < n;i ++) {for(int j = 0;j < m; j ++) {if(grid[i][j] == 0) allland = false;if(grid[i][j] == 1) {count = 0;//count需要重新设为0，为下一块岛屿做准备dfs(grid,i,j,mark,count);//gridnum存的是面积gridnum[mark] = count;mark ++;}}}if(allland) {cout<<n * m<<endl;return 0;}//遍历所有为零的点，并把它变成1以求面积和int result = 0;//取最大的面积unordered_set<int> visitedland;//标记访问过的岛屿的标号（mark）for(int i = 0;i < n;i ++) {for(int j = 0;j < m;j ++) {if(grid[i][j] == 0) {int count = 1;visitedland.clear();//每次用清零for(int k= 0;k < 4;k ++) {//查看上下左右是否有岛屿int nextx = i + dir[k][0];int nexty = j + dir[k][1];if(nextx < 0 || nextx == grid.size() || nexty < 0 || nexty == grid[0].size()) continue;if (visitedland.count(grid[nextx][nexty])) continue;count += gridnum[grid[nextx][nexty]];visitedland.insert(grid[nextx][nexty]);}result = max(result,count);}}}cout<<result;return 0;
}难点：
1.如grid里面没有海洋时，要返回n * m，对应代码中allland变量。
2.count的使用，因为不能用全局变量所以要把count传递给子函数，因为要在子函数中进行更改所以需要加上地址符。
3.哈希表里的地图gridnum将岛屿号和岛屿的面积联系起来用于后面求面积的最大值
4.在求面积的最大值时，用到的哈希表landvisted用于记录被添加的岛屿编号，防止重复添加。