【递归、搜索与回溯】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);
            }
        }
    }
};

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

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

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

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

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

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