【递归、搜索与回溯】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数组，当遇到未访问的陆地时：
- 统计岛屿数量
- 以该位置为起点进行深度优先遍历，遍历整个连通块
- 将整个连通块中的所有陆地都标记为已访问
编写代码
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）
题目描述
算法原理
- 统计太平洋水流：以紧邻太平洋的水域（第一行和第一列）为起点逆着水流的方向（>=）进行深度优先遍历，将DFS访问过的水域标记在pacific哈希表。
- 统计大西洋水流：以紧邻大西洋的水域（最后一行和最后一列）为起点逆着水流的方向（>=）进行深度优先遍历，将DFS访问过的水域标记在atlantic哈希表。
- 找到太平洋和大西洋水流的交集，返回结果。
编写代码
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;}
};