当前位置:   article > 正文

【递归、搜索与回溯】DFS解决FloodFill算法

【递归、搜索与回溯】DFS解决FloodFill算法

一、经验总结

之前我们已经研究过了BFS解决FloodFill算法:【优选算法】BFS解决FloodFill算法-CSDN博客

DFS只是遍历顺序发生了变化,其他需要注意的点大差不差。


二、相关编程题

2.1 图像渲染

题目链接

733. 图像渲染 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

以给定的初始坐标为起点开始进行DFS,将遍历到的每个位置都修改为新的颜色值(可以防止重复遍历)。需要注意的是,如果修改前后的颜色值相同则会出现重复遍历以至于死循环的结果,所以要进行特殊处理。

编写代码

class Solution {
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    int m, n, oldcolor, newcolor;
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        m = image.size(), n = image[0].size();
        newcolor = color, oldcolor = image[sr][sc];
        image[sr][sc] = newcolor;
        DFS(image, sr, sc);
        return image;
    }

    void DFS(vector<vector<int>>& image, int sr, int sc)
    {
        for(int i = 0; i < 4; ++i)
        {
            int x=sr+dx[i], y = sc+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && image[x][y]==oldcolor)
            {
                image[x][y] = newcolor;
                DFS(image, x, y);
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27

2.2 岛屿数量

题目链接

200. 岛屿数量 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

遍历grid数组,当遇到未访问的陆地时:

  1. 统计岛屿数量
  2. 以该位置为起点进行深度优先遍历,遍历整个连通块
  3. 将整个连通块中的所有陆地都标记为已访问

编写代码

class Solution {
    int m, n, ret;
    vector<vector<bool>> visited;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int numIslands(vector<vector<char>>& grid) {
        m = grid.size(), n = grid[0].size();
        visited.resize(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j]=='1' && !visited[i][j])
                {
                    ++ret;
                    DFS(grid, i, j);
                }
            }
        }
        return ret;
    }

    void DFS(vector<vector<char>>& grid, int r, int c)
    {
        visited[r][c] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && grid[x][y]=='1' && !visited[x][y])
            {
                DFS(grid, x, y);
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36

2.3 岛屿的最大面积

题目链接

695. 岛屿的最大面积 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

同上一题基本相同,之不过需要多添加一个变量用于统计每个岛屿的面积。最终返回岛屿的最大面积。

编写代码

class Solution {
    int m, n, ret, tmp;
    vector<vector<bool>> visited;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        visited.resize(m, vector<bool>(n, false));
        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(grid[i][j]==1 && !visited[i][j])
                {
                    tmp = 0;
                    DFS(grid, i, j);
                    ret = max(tmp, ret);
                }
            }
        }
        return ret;
    }

    void DFS(vector<vector<int>>& grid, int r, int c)
    {
        ++tmp;
        visited[r][c] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && !visited[x][y])
            {
                DFS(grid, x, y);
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38

2.4 被围绕的区域

题目链接

130. 被围绕的区域 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

在这里插入图片描述

编写代码

class Solution {
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
public:
    void solve(vector<vector<char>>& board) {
        m = board.size(), n = board[0].size();
        for(int i = 0; i < m; ++i)
        {
            if(board[i][0] == 'O') DFS(board, i, 0);
            if(board[i][n-1] == 'O') DFS(board, i, n-1);
        }
        for(int j = 0; j < n; ++j)
        {
            if(board[0][j] == 'O') DFS(board, 0, j);
            if(board[m-1][j] == 'O') DFS(board, m-1, j);
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(board[i][j] == 'O') board[i][j] = 'X';
                if(board[i][j] == '.') board[i][j] = 'O';
            }
        }
    }

    void DFS(vector<vector<char>>& board, int r, int c)
    {
        board[r][c] = '.';
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O')
            {
                DFS(board, x, y);
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41

2.5 太平洋大西洋水流问题

题目链接

417. 太平洋大西洋水流问题 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

  1. 统计太平洋水流:以紧邻太平洋的水域(第一行和第一列)为起点逆着水流的方向(>=)进行深度优先遍历,将DFS访问过的水域标记在pacific哈希表。
  2. 统计大西洋水流:以紧邻大西洋的水域(最后一行和最后一列)为起点逆着水流的方向(>=)进行深度优先遍历,将DFS访问过的水域标记在atlantic哈希表。
  3. 找到太平洋和大西洋水流的交集,返回结果。

编写代码

class Solution {
    int m, n;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    vector<vector<bool>> pacific;
    vector<vector<bool>> atlantic;
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m = heights.size(), n = heights[0].size();
        pacific.resize(m, vector<bool>(n, false));
        atlantic.resize(m, vector<bool>(n, false));
        vector<vector<int>> ret;
        for(int i = 0; i < m; ++i)
        {
            if(!pacific[i][0]) DFS(heights, pacific, i, 0);
            if(!atlantic[i][n-1]) DFS(heights, atlantic, i, n-1);
        }
        for(int j = 0; j < n; ++j)
        {
            if(!pacific[0][j]) DFS(heights, pacific, 0, j);
            if(!atlantic[m-1][j]) DFS(heights, atlantic, m-1, j);
        }

        for(int i = 0; i < m; ++i)
        {
            for(int j = 0; j < n; ++j)
            {
                if(pacific[i][j] && atlantic[i][j])
                {
                    ret.push_back({i, j});
                }
            }
        }
        return ret;
    }

    void DFS(vector<vector<int>>& heights, vector<vector<bool>>& ocean, int r, int c)
    {
        ocean[r][c] = true;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && !ocean[x][y] && heights[x][y]>=heights[r][c])
            {
                DFS(heights, ocean, x, y);
            }
        }
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49

2.6 扫雷游戏

题目链接

529. 扫雷游戏 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

见代码

编写代码

class Solution {
    //注意:有8个方向的向量
    int dx[8] = {0, 0, 1, -1, 1, -1, 1, -1}; 
    int dy[8] = {1, -1, 0, 0, 1, -1, -1, 1};
    int m, n;
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        int sr = click[0], sc = click[1];
        if(board[sr][sc] == 'M') //点中雷直接返回
        {
            board[sr][sc] = 'X';
            return board;
        }
        m = board.size(), n = board[0].size();
        DFS(board, sr, sc);
        return board;
    }

    void DFS(vector<vector<char>>& board, int r, int c)
    {
        //统计点击位置周围的地雷数量
        int cnt = 0;
        for(int i = 0; i < 8; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M')
                ++cnt;
        }

        if(cnt == 0) //周围没有地雷,向四周继续拓展
        {
            board[r][c] = 'B';
            for(int i = 0; i < 8; ++i)
            {
                int x=r+dx[i], y=c+dy[i];
                if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='E')
                    DFS(board, x, y);
            }
        }
        else //周围有地雷,标记周围地雷的数量
            board[r][c] = cnt+'0';
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

2.7 衣橱整理

题目链接

LCR 130. 衣橱整理 - 力扣(LeetCode)

题目描述

在这里插入图片描述

算法原理

编写代码

class Solution {
    int ret;
    int _m, _n, _cnt;
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};
    bool visited[100][100];
public:
    int wardrobeFinishing(int m, int n, int cnt) {
        _m = m, _n = n, _cnt = cnt;
        DFS(0, 0);
        return ret;
    }

    void DFS(int r, int c)
    {
        visited[r][c] = true;
        ++ret;
        for(int i = 0; i < 4; ++i)
        {
            int x=r+dx[i], y=c+dy[i];
            if(x>=0 && x<_m && y>=0 && y<_n && !visited[x][y] && digit(x)+digit(y)<=_cnt)
                DFS(x, y);
        }
    }

    int digit(int num)
    {
        int sum = 0;
        while(num > 0)
        {
            sum+=num%10;
            num/=10;
        }
        return sum;
    }
};
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/黑客灵魂/article/detail/786971
推荐阅读
相关标签
  

闽ICP备14008679号