【每日刷题】Day143

【每日刷题】Day143

🥕个人主页：开敲🍉

🔥所属专栏：每日刷题🍍

🌼文章目录🌼

1. 200. 岛屿数量 - 力扣（LeetCode）

2. LCR 105. 岛屿的最大面积 - 力扣（LeetCode）

3. 130. 被围绕的区域 - 力扣（LeetCode）

1. 200. 岛屿数量 - 力扣（LeetCode）

//思路：floodfill算法+哈希

class Solution {

public:

    int ans = 0;

    void dfs(vector<vector<char>>& grid,int i,int j,vector<vector<bool>>& hash)

    {

        if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||grid[i][j]=='0')//回溯：越界 || 当前位置为字符 '0'

            return;

       

        hash[i][j] = true;//每访问一个 ‘1’ ，将该位置设为 "已访问"

//上、下、左、右递归

        if(i-1>=0&&!hash[i-1][j])

            dfs(grid,i-1,j,hash);

        if(i+1<=grid.size()&&!hash[i+1][j])

            dfs(grid,i+1,j,hash);

        if(j-1>=0&&!hash[i][j-1])

            dfs(grid,i,j-1,hash);

        if(j+1<=grid[0].size()&&!hash[i][j+1])

            dfs(grid,i,j+1,hash);

    }

    int numIslands(vector<vector<char>>& grid)

    {

        vector<vector<bool>> hash(301,vector<bool>(301));

        for(int i = 0;i<grid.size();i++)

        {

            for(int j = 0;j<grid[0].size();j++)

            {

                if(!hash[i][j]&&grid[i][j]=='1')//在该位置进行 dfs 的条件

                {

                    ans++;

                    dfs(grid,i,j,hash);

                }

            }

        }

        return ans;

    }

};

2. LCR 105. 岛屿的最大面积 - 力扣（LeetCode）

//思路：floodfill算法+哈希

//这些题的思路基本都是一样的，实在是没必要重复画那么多决策树。

//本题的思路与上一题 "岛屿数量" 是完全类似的：

//遍历数组，遇到没有访问过的位置 并且 该位置值为1，在该位置进行 dfs，计算当前位置所组成岛屿的面积；dfs结束后与结果进行比较，记录较大值。

class Solution {

public:

    int ans = 0;

    void dfs(vector<vector<int>>& grid,int i,int j,vector<vector<bool>>& hash,int& tmp)

    {

        if(i>=grid.size()||i<0||j>=grid[0].size()||j<0||!grid[i][j])//回溯：越界 || 当前位置值为0

            return;

        hash[i][j] = true;//每到一个 1 位置，将该位置设为 "已访问"

        tmp++;//统计岛屿面积

//上、下、左、右依次递归

        if(i-1>=0&&!hash[i-1][j])

            dfs(grid,i-1,j,hash,tmp);

        if(i+1<=grid.size()&&!hash[i+1][j])

            dfs(grid,i+1,j,hash,tmp);

        if(j-1>=0&&!hash[i][j-1])

            dfs(grid,i,j-1,hash,tmp);

        if(j+1<=grid[0].size()&&!hash[i][j+1])

            dfs(grid,i,j+1,hash,tmp);

    }

    int maxAreaOfIsland(vector<vector<int>>& grid)

    {

        vector<vector<bool>> hash(51,vector<bool>(51));

        for(int i = 0;i<grid.size();i++)

        {

            for(int j = 0;j<grid[0].size();j++)

            {

                int tmp = 0;//tmp用于统计面积

                if(!hash[i][j]&&grid[i][j])

                {

                    dfs(grid,i,j,hash,tmp);

                    ans = ans>tmp?ans:tmp;//比较取较大值

                }

            }

        }

        return ans;

    }

};

3. 130. 被围绕的区域 - 力扣（LeetCode）

//思路：floodfill+哈希

//本题思路还是类似，唯一的区别在于：我们如何区分哪些相连的 'O' 区域需要填充为 'X'，哪些不需要？

class Solution {

public:

    void dfs(vector<vector<char>>& board,int i,int j,vector<vector<bool>>& hash)

    {

        if(i>=board.size()||i<0||j>=board[0].size()||j<0||board[i][j]=='X')//回溯：越界 || 当前位置为 'X'

            return;

        hash[i][j] = true;//将当前位置标记为 "已访问"

        board[i][j] = 'X';//并将当前位置的 'O' 更改为 'X'

//上、下、左、右递归

        if(i-1>=0&&!hash[i-1][j])

            dfs(board,i-1,j,hash);

        if(i+1<=board.size()&&!hash[i+1][j])

            dfs(board,i+1,j,hash);

        if(j-1>=0&&!hash[i][j-1])

            dfs(board,i,j-1,hash);

        if(j+1<=board[0].size()&&!hash[i][j+1])

            dfs(board,i,j+1,hash);

    }

    void solve(vector<vector<char>>& board)

    {

        vector<vector<bool>> hash(201,vector<bool>(201));

        vector<vector<char>> copy_board = board;//"替死鬼"数组，帮助我们标记 "不能更改" 的区域

//遍历 列边界，标记 列边界的 "不能更改" 的区域

        for(int i = 0;i<copy_board.size();i++)

        {

            if(copy_board[i][0]=='O')

                dfs(copy_board,i,0,hash);

            if(copy_board[i][copy_board[0].size()-1]=='O')

                dfs(copy_board,i,copy_board[0].size()-1,hash);

        }

       

//遍历 行边界，标记 行边界的 "不能更改" 的区域

        for(int j = 0;j<copy_board[0].size();j++)

        {

            if(copy_board[0][j]=='O')

                dfs(copy_board,0,j,hash);

            if(copy_board[copy_board.size()-1][j]=='O')

                dfs(copy_board,copy_board.size()-1,j,hash);

        }

//"替死鬼"数组帮我们标记了好了 "不能更改" 的区域，这里放心大胆地遍历board数组进行更改即可

        for(int i = 0;i<board.size();i++)

        {

            for(int j = 0;j<board[0].size();j++)

            {

                if(!hash[i][j]&&board[i][j]=='O')

                    dfs(board,i,j,hash);

            }

        }

    }

};