第十一章：图论part03

任务日期：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;//每次bfs
    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] = 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变成0
    for(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;
        }
    }
    
    //最后输出grid
    for(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用于记录被添加的岛屿编号，防止重复添加。