floodfill算法题目

前言

大家好，我是jiantaoyab，在下面的题目中慢慢体会floodFill算法，虽然是新的算法，但是用的思想和前面的文章几乎一样，代码格式也几乎一样，但不要去背代码

图像渲染

https://leetcode.cn/problems/flood-fill/

解析

代码

可以看到代码这部分，是不是和前面的文章的挺像的

class Solution {int m, n;int pre_color;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:void dfs(vector<vector<int>>& image, int sr, int sc, int color){image[sr][sc] = color;for(int d = 0; d < 4; d++){int x = sr + dx[d], y = sc + dy[d];if((x >= 0 && x < m) && (y >= 0 && y < n) &&  image[x][y] == pre_color){image[x][y] = color;dfs(image, x, y, color);}}}vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {m = image.size(), n = image[0].size();pre_color = image[sr][sc];if(image[sr][sc] == color) return image;dfs(image, sr, sc, color);return image; }
};

岛屿数量

https://leetcode.cn/problems/number-of-islands/

解析

代码

class Solution {int m, n;vector<vector<bool>> check;int dx[4]= {0, 0, 1, -1};int dy[4]= {1, -1, 0, 0};
public:void dfs(vector<vector<char>>& grid, int i, int j){check[i][j] = true; //从i，j位置来的for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if((x >= 0 && x < m) && (y >= 0 && y < n)  && grid[x][y] == '1' && !check[x][y]){dfs(grid, x, y);}}}int numIslands(vector<vector<char>>& grid) {int m = grid.size(), n = grid[0].size();check = vector<vector<bool>> (m ,vector<bool>(n));int ret = 0;//把整个grid遍历一次for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){//如果是一个岛屿而且是没有出现过的if(grid[i][j] == '1' && !check[i][j]){ret++;dfs(grid, i, j);}}}return ret;}
};

岛屿的最大面积

https://leetcode.cn/problems/ZL6zAn/

解析

大家看这个图就知道题目求的是什么了，比起上一题，多个统计数

代码

class Solution {    int m, n;bool check[51][51];int dx[4] = {1,-1,0,0};int dy[4] = {0, 0,1,-1};int count;
public:void dfs(vector<vector<int>>& grid, int i, int j){count++;check[i][j] = true;for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1  && !check[x][y]){dfs(grid, x, y);}}}int maxAreaOfIsland(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();int ret = 0;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(!check[i][j] && grid[i][j] == 1){count = 0;dfs(grid, i, j);ret = max(ret, count);}}}return ret;}
};

被围绕的区域

https://leetcode.cn/problems/surrounded-regions/

解析

代码

class Solution {int m, n;int dx[4] = {0,0,1,-1};int dy[4] = {1,-1,0,0};
public:void dfs(vector<vector<char>>& board, int i, int j){board[i][j] = 'a';for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O'){dfs(board, x, y);}}}void solve(vector<vector<char>>& board) {m = board.size(), n = board[0].size();//把左右2列边界处理了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 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] == 'a') board[i][j] = 'O';else if(board[i][j] == 'O') board[i][j] = 'X';}}}
};

太平洋大西洋水流问题

https://leetcode.cn/problems/pacific-atlantic-water-flow/

解析

代码

class Solution {int m, n;int dx[4] = {1, -1, 0, 0};int dy[4] = {0,  0, 1, -1};
public:void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>&check){check[i][j] = true;for(int d = 0; d < 4; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n &&  !check[x][y] &&heights[x][y] >= heights[i][j] ){dfs(heights, x, y, check);}}}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));//处理pacfor(int j = 0; j < n; j++) dfs(heights, 0, j, pac);for(int i = 0; i < m; i++) dfs(heights, i, 0, pac);//处理altfor(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(pac[i][j] && atl[i][j])ret.push_back({i, j});}}return ret;}
};

扫雷游戏

https://leetcode.cn/problems/minesweeper/

解析

代码

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:void dfs(vector<vector<char>>& board, int i, int j){int count = 0; //地雷个数//统计地雷个数for(int d = 0; d < 8; d++){int x = i + dx[d], y = j + dy[d];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 d = 0; d < 8; d++){int x = i + dx[d], y = j + dy[d];if(x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E'){dfs(board, x, y);}}}}vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {m = board.size(), n = board[0].size();int x = click[0], y = click[1];//开局中地雷if(board[x][y] == 'M'){board[x][y] = 'X';return board;}dfs(board, x, y);return board;}
};