力扣刷题记录(29)LeetCode:695、1020、130

发布时间:2024年01月07日

695.?岛屿的最大面积

这道题和计算岛屿周长类似,在这里dfs的功能就是由一块陆地出发,找出这块陆地所在的岛屿并返回岛屿面积。

class Solution {
public:
    int dfs(vector<vector<int>>& grid,int i,int j)
    {
        if(i<0||i>=grid.size()) return 0;
        if(j<0||j>=grid[0].size())  return 0;
        if(grid[i][j]==2||grid[i][j]==0)   return 0;
        grid[i][j]=2;
        return 1+dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1);
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int ans=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                if(grid[i][j]==1)
                    ans=max(dfs(grid,i,j),ans);
            }
        }
        return ans;
    }
};

?1020.?飞地的数量

?

?这和求岛屿面积类似,唯一的不同点是与边界相连的岛屿不用计算面积。因此在遍历岛屿的过程中如果遇到与边界相连的岛屿我们就返回一个负数,如果岛屿没有与边界相连我们就返回陆地的数量。

class Solution {
public:
    int dfs(vector<vector<int>>& grid,int i,int j)
    {
        if(i<0||i>=grid.size())     return -250000;
        if(j<0||j>=grid[0].size())  return -250000;
        if(grid[i][j]==2||grid[i][j]==0)    return 0;
        grid[i][j]=2;
        return 1+dfs(grid,i-1,j)+dfs(grid,i+1,j)+dfs(grid,i,j-1)+dfs(grid,i,j+1);
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int ans=0;
        for(int i=0;i<grid.size();i++)
        {
            for(int j=0;j<grid[0].size();j++)
            {
                int num=0;
                if(grid[i][j]==1)
                    num=dfs(grid,i,j);
                if(num>0)
                    ans+=num;
            }
        }
        return ans;
    }
};

130.?被围绕的区域

实际上这题还是在求飞地,把飞地变成水域。我们需要申请一个空间来记录我们遍历过的元素。dfs的功能是判断该岛屿是否是飞地,如果是我们就将其变成水域。

class Solution {
public:
    bool dfs(vector<vector<char>>& board,int i,int j,vector<vector<bool>>& isVisited)
    {
        if(i<0||i>=board.size())    return false;
        if(j<0||j>=board[0].size()) return false;
        if(isVisited[i][j]) return true;
        if(board[i][j]=='X')  return true;
        isVisited[i][j]=true;
        bool up=dfs(board,i-1,j,isVisited);
        bool down=dfs(board,i+1,j,isVisited);
        bool left=dfs(board,i,j-1,isVisited);
        bool right=dfs(board,i,j+1,isVisited);
        return up&&down&&left&&right;
    }
    void fill(vector<vector<char>>& board,int i,int j)
    {
        if(i<0||i>=board.size())    return;
        if(j<0||j>=board[0].size()) return;
        if(board[i][j]=='X')    return;
        board[i][j]='X';
        fill(board,i-1,j);
        fill(board,i+1,j);
        fill(board,i,j-1);
        fill(board,i,j+1);
    }
    void solve(vector<vector<char>>& board) {
        vector<vector<bool>> isVisited(board.size(),vector<bool>(board[0].size(),false));
        for(int i=0;i<board.size();i++)
        {
            for(int j=0;j<board[0].size();j++)
            {
                if(board[i][j]=='O'&&isVisited[i][j]==false)
                    if(dfs(board,i,j,isVisited))
                        fill(board,i,j);
            }
        }
    }
};

?

文章来源:https://blog.csdn.net/weixin_61759589/article/details/135438063
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。