算法|图论 2

LeetCode 695- 岛屿的最大面积

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述：给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

解题思路

思路一（深度优先遍历）：

1. 首先确定递归函数的参数，返回值。本题要路径，我们直接设置两个全局变量res和tmp，这样可以不用写太多参数传递。返回值就是void，参数需要图和一个x和y来记录当前在哪个岛屿。下次从这个岛屿开始走的。
2. 确定终止条件，本题按我们的逻辑，先进入循环再判断是否应该终止，那么终止条件就是：当超出网格范围 或 该岛屿已经是海洋 就终止。
3. 单层处理逻辑，每次将当前岛屿淹没，并且让这片岛屿的面积++（因为我们是确定了当前是陆地才会进入下层递归）。

class Solution {
public:
int res = 0;//记录最大面积
int tmp = 0;//当前这片岛屿的面积
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    dfs(grid, i, j);
                    //当这次递归结束的时候，说明这片岛屿已经全部被淹没了，此时我们可以记录一下
                    //这片岛屿的面积，并将tmp置为0，也就是下一片岛屿从新计算大小
                    res = max(res,tmp);
                    tmp = 0;
                }
            }
        }
        return res;
    }
public:
    void dfs(vector<vector<int>>& grid, int i, int j) {
        if (i < 0 || j < 0  || i >= grid.size() || j >= grid[0].size() ||  grid[i][j] != 1){
            return;
        }
        grid[i][j] = 0;
        //当前如果是陆地那么就让岛屿大小++
        tmp++;
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

思路二（广度优先遍历）：

与之前一题一样，就是多一个计算每片岛屿面积的tmp

class Solution {
public:
    int res = 0;
    int tmp = 0;
    int dir[4][2] = {0,1,1,0,-1,0,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j] == 1){
                    bfs(grid,i,j);
                    res = max(res,tmp);
                    tmp = 0;
                }
            }
        }
        return res;
    }
    void bfs(vector<vector<int>> &grid,int x,int y){
        queue<pair<int,int>> que;
        que.push({x,y});
        grid[x][y] = 0;
        tmp++;//这里也要面积++，因为第一次进入也淹没了一个小岛屿。
        while(!que.empty()){
            pair<int,int> cur = que.front();
            que.pop();
            int curx = cur.first;
            int cury = cur.second;
            for(int i=0;i<4;i++){
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1];
                if(nextx < 0 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size() ||grid[nextx][nexty] != 1) continue;
                que.push({nextx,nexty});
                grid[nextx][nexty] = 0;
                tmp++;
            }
        }
    }
};

总结：

• 深搜和广搜的问题，这题的广搜需要注意，只要淹没就得加面积的。

LeetCode 1020- 飞地的数量

题目链接：力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台

题目描述：给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

解题思路

思路一（深度优先遍历）：

1. 首先确定递归函数的参数，返回值。本题不需要这些。不过这题我们要设置一个全局变量cango表示是否能走到界外。为false不能走到界外，为true则可以走到界外。
2. 确定终止条件，本题按我们的逻辑，先进入循环再判断是否应该终止，那么终止条件就是：当超出网格范围 或 当前遍历的是海洋 就终止。不过这里需要注意，这道题目需要求的是不能走到界外的岛屿的数量。所以终止条件处理的时候有些区别。当出界的时候就将cango设置为true表示可以走出界并返回。当遇到的是海洋，就直接返回。

1. 单层处理逻辑，每次我们将当前岛屿的值设置为0，模拟为被淹没，并且去淹没当前节点的上下左右相邻的节点。为1的节点为陆地状态，并且将tmp++，表示相连的岛屿数量加一。在每次递归完出来的时候，说明走完了这一片岛屿，我们可以看看是否能走出界，不能则将tmp 加到res中，并且将tmp置为0（cango不做操作，因为默认不能走出去）。可以则将cango置为false，并且将tmp置为0。直到这片海域没有岛屿为止。

class Solution {
public:
    int res = 0;
    int tmp = 0;
    bool cango = false;//标记当前这片岛屿能否走到界外
    void dfs(vector<vector<int>> &grid,int x,int y){
        //若到达界外，则标记为true，返回
        if(x < 0 || y < 0 || x >= grid.size() || y >= grid[0].size()){
             cango = true;
             return ;
        }
        //若是海洋，也返回
        if(grid[x][y] == 0) return;
    	//将岛屿淹没
        grid[x][y] = 0;
        //这片岛屿数量加一
        tmp ++;
        dfs(grid,x+1,y);
        dfs(grid,x-1,y);
        dfs(grid,x,y+1);
        dfs(grid,x,y-1);
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                //若遇到岛屿，则进行深度优先遍历
                if(grid[i][j] == 1){
                    dfs(grid,i,j);
                    //若标记为不能走到边界，则将tmp加到结果中
                    if(cango == false){
                        res += tmp;
                        //将tmp清零
                        tmp = 0;
                    }else{
                        //若无法走到边界，则将cango改为默认值false
                        tmp = 0;
                        cango = false;
                    }
                }
            }
        }
        return res;
    }
};

思路二（广度优先遍历）：

就是多了一个不能走出界则将岛屿数加到结果中的操作。

class Solution {
public:
    int tmp = 0;
    int res = 0;
    bool cango = false;//标记是否能走到界外
    int dir[4][2] = {0,1,1,0,-1,0,0,-1};
    void bfs(vector<vector<int>> &grid,int x,int y){
        queue<pair<int,int>> que;//存储对组的队列，存坐标用的
        que.push({x,y});//压入当前的坐标
        grid[x][y] = 0;//淹没当前岛屿
        tmp ++;//只要有淹没，就tmp++
        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 || nexty < 0 || nextx >= grid.size() || nexty >= grid[0].size()){
                    cango = true;
                    continue;
                }
                if(0 == grid[nextx][nexty]) continue;
                tmp++;
                que.push({nextx,nexty});
                grid[nextx][nexty] = 0;
            }
        }
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int m = grid.size(),n = grid[0].size();
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j] == 1){
                    bfs(grid,i,j);
                    if(false == cango){
                        res += tmp;
                    }else{
                        cango = false;
                    }
                    tmp = 0;
                }
            }
        }
        return res;
    }
};

总结：

• 多了一个加岛屿的操作。