企业如何对自己的网站进行建设,网页版qq空间电脑版,泰安网站建设培训,在线赚钱平台前言
大家好#xff0c;我是jiantaoyab#xff0c;在下面的题目中慢慢体会floodFill算法#xff0c;虽然是新的算法#xff0c;但是用的思想和前面的文章几乎一样#xff0c;代码格式也几乎一样#xff0c;但不要去背代码
图像渲染 https://leetcode.cn/problems/flood…前言
大家好我是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(vectorvectorint 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);}}}vectorvectorint floodFill(vectorvectorint 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;vectorvectorbool check;int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};
public:void dfs(vectorvectorchar grid, int i, int j){check[i][j] true; //从ij位置来的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(vectorvectorchar grid) {int m grid.size(), n grid[0].size();check vectorvectorbool (m ,vectorbool(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(vectorvectorint 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(vectorvectorint 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(vectorvectorchar 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(vectorvectorchar 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(vectorvectorint heights, int i, int j, vectorvectorboolcheck){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);}}}vectorvectorint pacificAtlantic(vectorvectorint heights) {m heights.size(), n heights[0].size();vectorvectorbool pac(m, vectorbool(n));vectorvectorbool atl(m, vectorbool(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);vectorvectorint 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(vectorvectorchar 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);}}}}vectorvectorchar updateBoard(vectorvectorchar board, vectorint 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;}
};
