• 代码随想录训练营Day 66|卡码网101.孤岛的总面积、102.沉没孤岛、103.水流问题、104.建造最大岛屿

    1.孤岛的总面积

    101. 孤岛的总面积 | 代码随想录

    代码：(bfs广搜)

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. int dir[4][2] = {1,0,0,1,-1,0,0,-1};
    6. int count;
    7. void bfs(vectorint>>&grid,int x,int y){
    8.     queueint,int>> que;
    9.     que.push({x,y});
    10.     grid[x][y] = 0; // 这里用grid的元素变为0来进行标记
    11.     count++;
    12.     while(!que.empty()){
    13.         pair<int,int> cur = que.front();
    14.         que.pop();
    15.         int curx = cur.first;
    16.         int cury = cur.second;
    17.         for(int i = 0; i < 4; i++){
    18.             int nextx = curx + dir[i][0];
    19.             int nexty = cury + dir[i][1];
    20.             if(nextx < 0||nextx >= grid.size()||nexty < 0 ||nexty >= grid[0].size()){
    21.                 continue;
    22.             }
    23.             if(grid[nextx][nexty] == 1){
    24.                 que.push({nextx,nexty});
    25.                 grid[nextx][nexty] = 0;
    26.                 count++;
    27.             }
    28.         }
    29.     }
    30. }
    31. int main(){
    32.     // 输入
    33.     int n,m;
    34.     cin >> n >> m;
    35.     vectorint>> grid(n,vector<int>(m,0));
    36.     for(int i = 0; i < n; i++){
    37.         for(int j = 0; j < m; j++){
    38.             cin >> grid[i][j];
    39.         }
    40.     }
    41.     // 处理
    42.     for(int i = 0; i < n; i++){
    43.         if(grid[i][0] == 1) bfs(grid,i,0);
    44.         if(grid[i][m - 1] == 1) bfs(grid,i,m - 1);
    45.     }
    46.     for(int j = 0; j < m; j++){
    47.         if(grid[0][j] == 1) bfs(grid,0,j);
    48.         if(grid[n - 1][j] == 1) bfs(grid,n - 1,j);
    49.     }
    50.     count = 0;
    51.     for(int i = 1; i < n - 1; i++){
    52.         for(int j = 1; j < m - 1; j++){
    53.             if(grid[i][j] == 1) bfs(grid,i,j);
    54.         }
    55.     }
    56.     // 输出
    57.     cout << count << endl;
    58. }

    思路：基础题型，这次直接在grid表上进行标记。先把靠近陆地的岛屿都标为0。将用于统计面积的变量的count置为0。接下来就可以排除临近陆地的岛屿，只统计孤岛的数量了。 

    易错点：我又犯错了。先是忘记写命名空间了，然后又是在if判断里二维数组我只写了一个下标，最后是找边界找错了，我的循环变量i是在变的，我只要固定另一个下标为临界值就好了。不知道为什么我把i放到了边界的运算里（。。脑子糊了）

    代码：（dfs 深搜）

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. int dir[4][2] = {1,0,0,1,-1,0,0,-1};
    6. int count;
    7. void bfs(vectorint>>&grid,int x,int y){
    8.     if(grid[x][y] == 0){
    9.         return;
    10.     }
    11.     grid[x][y] = 0;
    12.     count++;
    13.     for(int i = 0; i < 4; i++){
    14.         int nextx = x + dir[i][0];
    15.         int nexty = y + dir[i][1];
    16.         if(nextx < 0||nextx >= grid.size()||nexty < 0||nexty >= grid[0].size()){
    17.             continue;
    18.         }
    19.         bfs(grid,nextx,nexty);
    20.     }
    21. }
    22. int main(){
    23.     // 输入
    24.     int n,m;
    25.     cin >> n >> m;
    26.     vectorint>> grid(n,vector<int>(m,0));
    27.     for(int i = 0; i < n; i++){
    28.         for(int j = 0; j < m; j++){
    29.             cin >> grid[i][j];
    30.         }
    31.     }
    32.     // 处理
    33.     for(int i = 0; i < n; i++){
    34.         if(grid[i][0] == 1) bfs(grid,i,0);
    35.         if(grid[i][m - 1] == 1) bfs(grid,i,m - 1);
    36.     }
    37.     for(int j = 0; j < m; j++){
    38.         if(grid[0][j] == 1) bfs(grid,0,j);
    39.         if(grid[n - 1][j] == 1) bfs(grid,n - 1,j);
    40.     }
    41.     count = 0;
    42.     for(int i = 1; i < n - 1; i++){
    43.         for(int j = 1; j < m - 1; j++){
    44.             if(grid[i][j] == 1) bfs(grid,i,j);
    45.         }
    46.     }
    47.     // 输出
    48.     cout << count << endl;
    49. }

     思路：我的博客快做成个人错误大赏了。。。

    这次的错误是 在进行下标是否非法的判断的时候，我又写错了。一定要注意边界条件啊，以后检查的时候就应该找这种判断语句好好看看。

    2.沉没孤岛 

    102. 沉没孤岛 | 代码随想录

    代码：（深搜dfs）

    1. #include 
    2. #include 
    3. #include 
    4. using namespace std;
    5. int dir[4][2] = {1,0,0,1,-1,0,0,-1};
    6. int count;
    7. void bfs(vectorint>>&grid,int x,int y){
    8.     if(grid[x][y] == 2||grid[x][y] == 0){
    9.         return;
    10.     }
    11.     grid[x][y] = 2;
    12.     for(int i = 0; i < 4; i++){
    13.         int nextx = x + dir[i][0];
    14.         int nexty = y + dir[i][1];
    15.         if(nextx < 0||nextx >= grid.size()||nexty < 0||nexty >= grid[0].size()){
    16.             continue;
    17.         }
    18.         bfs(grid,nextx,nexty);
    19.     }
    20. }
    21. int main(){
    22.     // 输入
    23.     int n,m;
    24.     cin >> n >> m;
    25.     vectorint>> grid(n,vector<int>(m,0));
    26.     for(int i = 0; i < n; i++){
    27.         for(int j = 0; j < m; j++){
    28.             cin >> grid[i][j];
    29.         }
    30.     }
    31.     // 处理
    32.     // 将临近陆地的标为2 和 孤岛区分开
    33.     vectorbool>> visited(n,vector<bool>(m,false));
    34.     for(int i = 0; i < n; i++){
    35.         if(grid[i][0] == 1) bfs(grid,i,0);
    36.         if(grid[i][m - 1] == 1) bfs(grid,i,m - 1);
    37.     }
    38.     for(int j = 0; j < m; j++){
    39.         if(grid[0][j] == 1) bfs(grid,0,j);
    40.         if(grid[n - 1][j] == 1) bfs(grid,n - 1,j);
    41.     }
    42.     // 将孤岛沉没 将临近陆地的单元还原
    43.     for(int i = 0; i < n; i++){
    44.         for(int j = 0; j < m; j++){
    45.             if(grid[i][j] == 1) grid[i][j] = 0;
    46.             if(grid[i][j] == 2) grid[i][j] = 1;
    47.         }
    48.     }
    49.     // 输出
    50.     for(int i = 0; i < n; i++){
    51.         for(int j = 0; j < m; j++){
    52.             cout << grid[i][j] << " ";
    53.         }
    54.         cout << endl;
    55.     }
    56. }

    思路：这里比较巧妙的就是因为临近陆地的岛屿比较好判断，所以将其标记为2，只要与孤岛区别开就好了。接下来，就是把1变为0，把2变为1，输出就好了 

    3.水流问题

    103. 水流问题 | 代码随想录

    代码： (深搜dfs)

    1. #include 
    2. #include 
    3. using namespace std;
    4. int dir[4][2] = {0,1,1,0,0,-1,-1,0};
    5. void dfs(const vectorint>> &grid,vectorbool>> &visited,int x, int y){
    6.     if(visited[x][y]) return;
    7.     visited[x][y] = true;
    8.     for(int i = 0; i < 4; i++){
    9.         int nextx = x + dir[i][0];
    10.         int nexty = y + dir[i][4];
    11.         if(nextx < 0||nextx >= grid.size()||nexty < 0||nexty >= grid[0].size()){
    12.             continue;
    13.         }
    14.         // 必须从低到高
    15.         if(grid[nextx][nexty] < grid[x][y]) continue;
    16.         dfs(grid,visited,nextx,nexty);
    17.     }
    18.     return;
    19. }
    20. int main(){
    21.     //输入
    22.     int n,m;
    23.     cin >> n >> m;
    24.     vectorint>> grid(n,vector<int>(m,0));
    25.     for(int i = 0; i < n; i++){
    26.         for(int j = 0; j < m; j++){
    27.             cin >> grid[i][j];
    28.         }
    29.     }
    30.     // 处理
    31.     vectorbool>> firstBorder(n,vector<bool>(m,false));
    32.     vectorbool>> secondBorder(n,vector<bool>(m,false));
    33.     for(int i = 0; i < n; i++){
    34.         dfs(grid,firstBorder,i,0);
    35.         dfs(grid,secondBorderBorder,i,m - 1);
    36.     }
    37.     for(int j = 0; j < m; j++){
    38.         dfs(grid,firstBorder,0,j);
    39.         dfs(grid,secondBorder,n - 1,j);
    40.     }
    41.     // 输出
    42.     for(int i = 0; i < n; i++){
    43.         for(int j = 0; j < m; j++){
    44.             if(firstBorder[i][j]&&secondBorder[i][j]){
    45.                 cout << i << j << endl;
    46.             }
    47.         }
    48.     }
    49. }

     思路：这道题的优化很巧妙，因为从边界出发好判断，所以直接从边界出发，把边界可以到达的地方而且是递增的单元进行标记。上边界和下边界各用一套标记，当一个单元被标记两次时，就说明它时满足题意的。

    易错点：我自己写了半天，忘记写最重要的 if(grid[nextx][nexty] < grid[x][y]) continue;了。

    4.建造最大岛屿 

     104.建造最大岛屿 | 代码随想录

    代码： 

    1. #include 
    2. #include 
    3. #include 
    4. #include 
    5. using namespace std;
    6. int count;
    7. int dir[4][2] = {0,1,1,0,0,-1,-1,0};
    8. void dfs(vectorint>>&grid,vectorbool>>&visited,int x,int y,int mark){
    9.     if(visited[x][y]||grid[x][y] == 0) return;
    10.     visited[x][y] = true; // 标记已访问
    11.     grid[x][y] = mark; // 每个岛屿都有对应的标签
    12.     count++;
    13.     for(int i = 0; i < 4; i++){
    14.         int nextx = x + dir[i][0];
    15.         int nexty = y + dir[i][1];
    16.         if(nextx < 0||nextx >= grid.size()||nexty < 0||nexty >= grid[0].size()){
    17.             continue;
    18.         }
    19.         dfs(grid,visited,nextx,nexty,mark);
    20.     }
    21.     return;
    22. }
    23. int main(){
    24.     // 输入
    25.     int n,m;
    26.     cin >> n >> m;
    27.     vectorint>> grid(n,vector<int>(m,0));
    28.     for(int i = 0; i < n; i++){
    29.         for(int j = 0; j < m; j++){
    30.             cin >> grid[i][j];
    31.         }
    32.     }
    33.     // 处理
    34.     vectorbool>> visited(n,vector<bool>(m,false));
    35.     unordered_map<int,int> gridNum;
    36.     int mark = 2; // 记录岛屿的编号
    37.     bool isAllGrid = true; // 记录整个地图是否都是陆地(如果是，就没法添加陆地了)
    38.     for(int i = 0; i < n; i++){
    39.         for(int j = 0; j < m; j++){
    40.             if(grid[i][j] == 0) isAllGrid = false;
    41.             if(!visited[i][j] && grid[i][j] == 1){
    42.                 count = 0;
    43.                 dfs(grid,visited,i,j,mark);
    44.                 gridNum[mark] = count; // 记录每一个岛屿的面积
    45.                 mark++;
    46.             }
    47.         }
    48.     }
    49.     if(isAllGrid == true) {
    50.         cout << n*m << endl;
    51.         return 0;
    52.     }
    53.     // 根据所填陆地，计算周边岛屿面积之和
    54.     int result = 0;
    55.     unordered_set<int> visitedGrid; // 标记访问过的岛屿
    56.     for(int i = 0; i < n; i++){
    57.         for(int j = 0; j < m; j++){
    58.             count = 1; // 记录连接后的岛屿数量
    59.             visitedGrid.clear();
    60.             if(grid[i][j] == 0){
    61.                 for(int k = 0; k < 4; k++){
    62.                     int nexti = i + dir[k][0];
    63.                     int nextj = j + dir[k][1];
    64.                     if(nexti < 0||nexti >= grid.size()||nextj < 0||nextj >= grid[0].size()){
    65.                         continue;
    66.                     }
    67.                     if(visitedGrid.count(grid[nexti][nextj])) continue; // 添加过的岛屿不要重复添加
    68.                     count += gridNum[grid[nexti][nextj]];
    69.                     visitedGrid.insert(grid[nexti][nextj]);
    70.                 }
    71.             }
    72.             result = max(result,count);
    73.         }
    74.     }
    75.     cout << result << endl;
    76. }

    思路：这道题是先计算各个岛屿的面积，然后遍历每一块海域，将这块添加的单元与其临近的岛屿面积进行相加求和，保存里面的最大值。

    这道题真的是错死我了。。。这个涉及到很多细节，比如要考虑全是陆地的情况，要将每个岛屿进行面积和标号的映射，要在计算连接后的总面积的时候，将统计过的岛屿进行标记。。。我真的，太痛了。

  • 相关阅读:
    米软科技 | 推进医院智慧管理分级评估体系建立、提升评级
    【服务器安装Redis】Centos7离线安装redis
    高通SDX12：ASoC 音频框架浅析
    应用程序分类与相关基本概念介绍
    01-自动内存管理机制
    靠着这份1600多页的“Java面试突击核心”手册，我成功拿下了3个大厂offer
    css实现进度条
    基于FPGA的电子万年历设计
    tauri 开发
    Tlsr8258开发-修改蓝牙hid mouse
  • 原文地址：https://blog.csdn.net/weixin_64434454/article/details/139866733