【递归回溯之floodfill算法专题练习】
1. 图像渲染
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m, n;int oldcolor;
public:vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {oldcolor = image[sr][sc]; // 保存原始像素值m = image.size();n = image[0].size();if(image[sr][sc] == color)return image;// 先将起点位置修改为colorimage[sr][sc] = color;dfs(image, sr, sc, color);return image;}void dfs(vector<vector<int>>& image, int sr, int sc, int color){for(int k = 0; k < 4; k++){int x = dx[k] + sr;int y = dy[k] + sc;if(x >= 0 && x < m && y >= 0 && y < n && image[x][y] == oldcolor){image[x][y] = color;dfs(image, x ,y , color);}}}
};2. 岛屿数量
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};bool vis[301][301] = { false };int m, n;
public:int numIslands(vector<vector<char>>& grid) {int ret = 0;m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)// 如果陆地没有标记并且为1,统计结果if(!vis[i][j] && grid[i][j] == '1') {ret++;vis[i][j] = true;dfs(grid, i, j); // 把这块岛屿相连的陆地全都标记 }return ret; }void dfs(vector<vector<char>>& grid, int i, int j){for(int k = 0; k < 4; k++){int x = dx[k] + i;int y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[i][j] == '1'){vis[i][j] = true;dfs(grid, x ,y);}}}
};3. 岛屿的最大面积
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};bool vis[51][51] = { false };int m, n;int count = 0, ret = 0;
public:int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size();n = grid[0].size();for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)// 如果陆地没有标记并且为1,此时开始深搜if(!vis[i][j] && grid[i][j] == 1) {count = 0;dfs(grid, i, j); // 把这块岛屿相连的陆地全都标记并统计面积 ret = max(ret, count);}return ret;}void dfs(vector<vector<int>>& grid, int i, int j){count++;vis[i][j] = true;for(int k = 0; k < 4; k++){int x = dx[k] + i;int y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && grid[x][y] == 1){dfs(grid, x ,y);}}}
};4. 被围绕的区域
正难则反，我们可以四周开始向里面遍历，但凡能深搜到的，都是不能修改的，此时我们将遍历到的标记一下，其余的全部修改成x即可。
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m, n;
public:void solve(vector<vector<char>>& board) {m = board.size();n = board[0].size();// 1. 把边界的O相连的联通块，全部修改成.// 修改两行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++){if(board[i][0] == 'O') dfs(board, i, 0);if(board[i][n - 1] == 'O') dfs(board, i, n - 1);}// 2. 还原for(int i = 0; i < m; i++)for(int j = 0; j < n; j++){if(board[i][j] == '.') board[i][j] = 'O';else if(board[i][j] == 'O') board[i][j] = 'X';} }void dfs(vector<vector<char>>& board, int i, int j){board[i][j] = '.';for(int k = 0; k < 4; k++){int x = dx[k] + i;int y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){dfs(board, x ,y);}}}
};5. 太平洋大西洋水流问题
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {1, -1, 0, 0};int m, n;
public:vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {m = heights.size();n = heights[0].size();vector<vector<bool>> pac(m, vector<bool>(n));vector<vector<bool>> atl(m, vector<bool>(n));// 先处理第一行和第一列 - 太平洋for(int j = 0; j < n; j++) dfs(heights, 0, j, pac);for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);// 再处理最后一行和最后一列 - 大西洋for(int j = 0; j < n; j++) dfs(heights, m - 1, j, atl);for(int i = 0; i < m; i++) dfs(heights, i, n - 1, atl);vector<vector<int>> ret;for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(atl[i][j] && pac[i][j])ret.push_back({i, j});return ret;}void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& vis){vis[i][j] = true;for(int k = 0; k < 4; k++){int x = dx[k] + i;int y = dy[k] + j;if(x >= 0 && x < m && y >= 0 && y < n && !vis[x][y] && heights[i][j] <= heights[x][y]){dfs(heights, x, y, vis);}}}
};6. 扫雷游戏
class Solution {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) {m = board.size();n = board[0].size();// 如果运气背,起始位置就是地雷,直接返回int x = click[0];int y = click[1];if(board[x][y] == 'M'){board[x][y] = 'X';return board;}dfs(board, x, y);return board;}void dfs(vector<vector<char>>& board, int i, int j){// 先统计一下周围地雷的个数int count = 0;for(int k = 0; k < 8; k++){int x = dx[k] + i;int y = dy[k] + j;// M 表示地雷if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M'){count++;}}// 该位置处存在地雷if(count){// 存在地雷就不需要展开board[i][j] = count + '0';return;}else{ // 周围八个位置都要展开// 先把自己标记成空方块board[i][j] = 'B';for(int k = 0; k < 8; k++){int x = dx[k] + i;int y = dy[k] + j;// E 表示没有点击的位置if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y);}}}}
};7. 机器人的运动范围
class Solution {int dx[4] = {0, 0, -1, 1};int dy[4] = {-1, 1, 0, 0};int ret;bool vis[101][101] = { false };
public:int wardrobeFinishing(int m, int n, int cnt) {dfs(0, 0, m, n, cnt);return ret;}bool check(int i, int j, int cnt){// 求数位之和int tmp = 0;while(i){tmp += i % 10;i /= 10;}while(j){tmp += j % 10;j /= 10;}return tmp <= cnt;}void dfs(int i, int j, int m, int n, int cnt){ ret++;vis[i][j] = true;for(int k = 0; k < 4; k++){int x = i + dx[k];int y = j +dy[k];if(x >= 0 && x < m && y >=0 && y < n && !vis[x][y] && check(x,y,cnt)){dfs(x, y, m, n, cnt);}}}
};