力扣刷题记录（29）LeetCode：695、1020、130

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);
            }
        }
    }
};