【递归、搜索与回溯】FloodFill算法（二）

📝前言说明：

• 本专栏主要记录本人递归，搜索与回溯算法的学习以及LeetCode刷题记录，按专题划分
• 每题主要记录：（1）本人解法 + 本人屎山代码；（2）优质解法 + 优质代码；（3）精益求精，更好的解法和独特的思想（如果有的话）
• 文章中的理解仅为个人理解。如有错误，感谢纠错

🎬个人简介：努力学习ing
📋本专栏：C++刷题专栏
📋其他专栏：C语言入门基础，python入门基础，C++学习笔记，Linux
🎀CSDN主页 愚润泽

你可以点击下方链接，进行该专题内不同子专题的学习

题单汇总链接：点击 → 题单汇总

130. 被围绕的区域

题目链接：https://leetcode.cn/problems/surrounded-regions/description/

优质解

思路：

• 所有的不被包围的 O 都直接或间接与边界上的 O 相连。我们可以利用这个性质判断 O 是否在边界上.
• 对于每一个边界上的 O，我们以它为起点，标记所有与它直接或间接相连的字母 O。（就是先对边界的O，dfs一遍）
• 那最后剩下的O就是都被包围的，全部换成X

代码：

class Solution {
public:
    int m, n;
    void dfs(vector<vector<char>>& board, int x, int y)
    {
        if(x >= m || x < 0 || y >= n || y < 0 ||board[x][y] != 'O')
            return;
        board[x][y] = 'A';
        dfs(board, x + 1, y);
        dfs(board, x - 1, y);
        dfs(board, x, y + 1);
        dfs(board, x, y - 1);
    }
    void solve(vector<vector<char>>& board) 
    {
        m = board.size(); n = board[0].size();
        for(int j = 0; j < n; j++)
        {
            dfs(board, 0, j);
            dfs(board, m - 1, j);
        }
        for(int i = 1; i < m - 1; i++)
        {
            dfs(board, i, 0);
            dfs(board, i, n - 1);
        }
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(board[i][j] == 'A')
                    board[i][j] = 'O';
                else if(board[i][j] == 'O')
                    board[i][j] = 'X';
            }
        }
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(\max (m,n))$，递归深度为max(m,n)，每个栈内空间复杂度是O(1)

417. 太平洋大西洋水流问题

题目链接：https://leetcode.cn/problems/pacific-atlantic-water-flow/description/

优质解

思路：

• 间接法，逆向思维由海洋推陆地（从海洋往里面陆地走，如果可以到达，则代表该陆地的水可以流到海洋）
• 用两个数组分别记录当前位置能不能留到海洋，然后分别从边界元素开始dfs
• dfs的时候，如果遇到已经判断过的确保能流向海洋的位置（即：check里面为true），就不用再递归判断

代码：

class Solution {
public:
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    void dfs(vector<vector<int>>& heights, int x, int y, vector<vector<bool>>& check)
    {
        check[x][y] = true;
        for(int i = 0; i < 4; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < m && nx >= 0 && ny < n && ny >= 0 && !check[nx][ny] && heights[nx][ny] >= heights[x][y])
                dfs(heights, nx, ny, check);
        }
    }
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) 
    {
        m = heights.size(); n = heights[0].size();
        vector<vector<bool>> Pacific(m, vector<bool>(n));
        vector<vector<bool>> Atlantic(m, vector<bool>(n));
        // 填充 Pacific 和 Atlantic
        for(int i = 0; i < m; i++)
        {
            dfs(heights, i, 0, Pacific);
            dfs(heights, i, n - 1, Atlantic);
        }
        for(int j = 0; j < n; j++)
        {
            dfs(heights, 0, j, Pacific);
            dfs(heights, m - 1, j, Atlantic);
        }
        // 判断两个数组，获得答案
        vector<vector<int>> ans;
        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(Pacific[i][j] && Atlantic[i][j])
                    ans.push_back({i, j});
            }
        }
        return ans;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

529. 扫雷游戏

题目链接：https://leetcode.cn/problems/minesweeper/description/

个人解

思路：

• 把前面的题目搞懂了，这题理解好题意就不难

用时：15:00
屎山代码：

class Solution {
public:
    int m, n;
    int dx[8] = {0, 0, 1, -1, -1, -1, 1, 1};
    int dy[8] = {-1, 1, 0, 0, 1, -1, 1, -1};
    void dfs(vector<vector<char>>& board, int x, int y)
    {
        // 踩到雷，游戏结束
        if(board[x][y] == 'M')
        {
            board[x][y] = 'X';
            return;
        }
        // 没踩到雷，游戏继续
        else
        {
            int num = 0;
            for(int i = 0; i < 8; i++)
            {
                int nx = x + dx[i], ny = y + dy[i]; // 八个位置
                if(nx < m && nx >= 0 && ny < n && ny >= 0 && board[nx][ny] == 'M')
                        num++;
            }
            if(num)
            {
                board[x][y] = '0' + num;
                return;
            }
            else
            {
                board[x][y] = 'B';
                for(int i = 0; i < 8; i++)
                {
                    // 把周围的未被挖出的方块揭晓
                    int nx = x + dx[i], ny = y + dy[i]; // 八个位置
                    if(nx < m && nx >= 0 && ny < n && ny >= 0 && board[nx][ny] == 'E')
                        dfs(board, nx, ny);
                }
            }
        }
    }
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) 
    {
        m = board.size(); n = board[0].size();
        dfs(board, click[0], click[1]);
        return board;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

LCR 130. 衣橱整理

题目链接：https://leetcode.cn/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/description/

个人解

思路：

• 奖励题

用时：15:00
屎山代码：

class Solution {
public:
    int dx[2] = {0, 1};
    int dy[2] = {1, 0};
    int ans = 0;
    int m, n;
    vector<vector<bool>> check;
    int getnum(int c) // 获取一个数的各数位之和
    {
        int num = 0;
        while(c)
        {
            num += c % 10;
            c /= 10;
        }
        return num;
    }
    void dfs(int x, int y, int cnt)
    {
        // 首先检查边界条件 以及 是否访问过
        if(x < 0 || x >= m || y < 0 || y >= n || check[x][y])
            return;
        check[x][y] = true;
        if(getnum(x) + getnum(y) <= cnt)
            ans++;
        else return; // 当前位置不满足则返回，因为向下和向右肯定也不满足
        for(int i = 0; i < 2; i++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            dfs(nx, ny, cnt);
        }
    }
    int wardrobeFinishing(int r, int c, int cnt) 
    {
        m = r; n = c; check = vector<vector<bool>>(m, vector<bool>(n, false));
        dfs(0, 0, cnt);
        return ans;
    }
};

时间复杂度：$O(m\ast n)$
空间复杂度：$O(m\ast n)$

🌈我的分享也就到此结束啦🌈
要是我的分享也能对你的学习起到帮助，那简直是太酷啦！
若有不足，还请大家多多指正，我们一起学习交流！
📢公主，王子：点赞👍→收藏⭐→关注🔍
感谢大家的观看和支持！祝大家都能得偿所愿，天天开心！！！