目录1.图像渲染1.dfs2.bfs2.岛屿数量1.dfs2.bfs3.岛屿的最大面积1.dfs2.bfs4.被围绕的区域1.dfs2.bfs5.太平洋大西洋水流问题6.扫雷游戏本质就是找出性质相似的连通块1.图像渲染733. 图像渲染 - 力扣LeetCode1.dfs我们使用深度优先遍历去遍历即可也不需要返回值。值得注意的有两点1.如果起始位置的颜色和目标颜色相同直接返回即可。2.由于我们遍历是向上下左右遍历因此我们进入dfs函数之前需要把初始位置颜色给改了class Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; int initcolor; int aimcolor; vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { m image.size(); n image[0].size(); initcolor image[sr][sc]; aimcolor color; if(image[sr][sc] ! color) { image[sr][sc] color; dfs(image, sr, sc); } return image; } void dfs(vectorvectorint image, int x,int y) { for(int k 0; k 4; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n image[i][j] initcolor) { image[i][j] aimcolor; dfs(image,i,j); } } } };2.bfs只是更换遍历方式利用队列来进行层序遍历class Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; typedef pairint, int pii; vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { m image.size(); n image[0].size(); int initcolor image[sr][sc]; if(image[sr][sc] color)return image; queuepii q; q.push({sr, sc}); while(q.size()) { auto[a, b] q.front(); q.pop(); image[a][b] color; for(int k 0; k 4; k) { int i a dx[k]; int j b dy[k]; if(i 0 i m j 0 j n image[i][j] initcolor) { q.push({i,j}); } } } return image; } };2.岛屿数量200. 岛屿数量 - 力扣LeetCode1.dfs算法思路都是一样的。这里我们找到一块陆地就让ret。然后再把相连的所有陆地都标记起来这样子下次找岛屿时就不会找到相同的地块了。并不需要恢复路径。class Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; int check[310][310]; int ret 0; int numIslands(vectorvectorchar grid) { m grid.size(); n grid[0].size(); for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1 check[i][j] false) { check[i][j] true; dfs(grid, i, j); ret; } } } return ret; } void dfs(vectorvectorchar grid, int x, int y) { for(int k 0; k 4; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n grid[i][j] 1 check[i][j] false) { check[i][j] true; dfs(grid,i,j); } } } };2.bfsclass Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; int check[310][310]; int ret 0; int numIslands(vectorvectorchar grid) { m grid.size(); n grid[0].size(); for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1 check[i][j] false) { bfs(grid, i, j); ret; } } } return ret; } void bfs(vectorvectorchar grid, int x, int y) { queuepairint, int q; q.push({x, y}); check[x][y] true; while(q.size()) { auto[a, b] q.front(); q.pop(); for(int k 0; k 4; k) { int i a dx[k]; int j b dy[k]; if(i 0 i m j 0 j n grid[i][j] 1 check[i][j] false) { q.push({i , j}); check[i][j] true; } } } } };3.岛屿的最大面积LCR 105. 岛屿的最大面积 - 力扣LeetCode1.dfs这题代码和岛屿数量几乎一样。我们要记录岛屿的面积只需要定义一个全局的count变量每次dfs进入一块新的地之后把count即可。每次找到一块新的未遍历的地的时候先将count清零class Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; int check[55][55]; int ret 0; int count; int maxAreaOfIsland(vectorvectorint grid) { m grid.size(); n grid[0].size(); for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1 check[i][j] false) { count 0; check[i][j] true; dfs(grid, i, j); ret max(ret, count); } } } return ret; } void dfs(vectorvectorint grid, int x, int y) { count; for(int k 0; k 4; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n grid[i][j] 1 check[i][j] false) { check[i][j] true; dfs(grid,i,j); } } } };2.bfsclass Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; int check[55][55]; int ret 0; int count; int maxAreaOfIsland(vectorvectorint grid) { m grid.size(); n grid[0].size(); for(int i 0; i m; i) { for(int j 0; j n; j) { if(grid[i][j] 1 check[i][j] false) { count 0; bfs(grid, i, j); ret max(ret, count); } } } return ret; } void bfs(vectorvectorint grid, int x, int y) { count; check[x][y] true; queuepairint, int q; q.push({x, y}); while(q.size()) { auto[a,b] q.front(); q.pop(); for(int k 0; k 4; k) { int i a dx[k]; int j b dy[k]; if(i 0 i m j 0 j n grid[i][j] 1 check[i][j] false) { check[i][j] true; count; q.push({i,j}); } } } } };4.被围绕的区域130. 被围绕的区域 - 力扣LeetCode1.dfs题目的意思是把四周都围上‘X’的O变成‘X’。于是给我们的图中有两种情况需要分别讨论。这样会非常麻烦。因此我们正难则反遍历一遍四周遇到‘O’时进行一次深度优先遍历就能找出所有与边缘相连的‘O’。我们先把这些O改成‘.’。对四周进行遍历后我们再把‘.’重新还原变成‘O’把原来没有被改变的‘O’改成‘X’。class Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; void solve(vectorvectorchar board) { m board.size(); n board[0].size(); for(int i 0; i n; i) { if(board[0][i] O)dfs(board, 0, i); if(board[m-1][i] O)dfs(board, m - 1, i); } 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 i 0; i m; i) { for(int j 0; j n; j) { if(board[i][j] O) { board[i][j] X; } else if(board[i][j] .) { board[i][j] O; } } } } void dfs(vectorvectorchar board, int x, int y) { board[x][y] .; for(int k 0; k 4; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n board[i][j] O ) { board[i][j] .; dfs(board,i,j); } } } };2.bfsclass Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; void solve(vectorvectorchar board) { m board.size(); n board[0].size(); for(int i 0; i n; i) { if(board[0][i] O)bfs(board, 0, i); if(board[m-1][i] O)bfs(board, m - 1, i); } for(int i 0; i m; i) { if(board[i][0] O)bfs(board, i, 0); if(board[i][n - 1] O )bfs(board, i, n - 1); } for(int i 0; i m; i) { for(int j 0; j n; j) { if(board[i][j] O) { board[i][j] X; } else if(board[i][j] .) { board[i][j] O; } } } } void bfs(vectorvectorchar board, int x, int y) { board[x][y] .; queuepairint, int q; q.push({x, y}); while(q.size()) { auto [a, b] q.front(); q.pop(); for(int k 0; k 4; k) { int i a dx[k]; int j b dy[k]; if(i 0 i m j 0 j n board[i][j] O ) { board[i][j] .; q.push({i ,j}); } } } } };5.太平洋大西洋水流问题417. 太平洋大西洋水流问题 - 力扣LeetCode依然也是正难则反的思路。我们从头到位遍历一次数组每到一个位置就进行一次深度优先遍历的话复杂度太高。因此我们选择逆向从靠近海边的位置进行逆向查找。这样每个格子被标记到之后只会被查到一次。这里我们开两个数组分别标记能流到大西洋和太平洋的位置。为了辨识数组这里选择传了一个标记数字。class Solution { public: int dx[4] {0 , 0, -1, 1}; int dy[4] {1 , -1 ,0 , 0}; int m, n; int check1[210][210]; int check2[210][210]; vectorvectorint ret; vectorvectorint pacificAtlantic(vectorvectorint board) { m board.size(); n board[0].size(); for(int i 0; i n; i) { check1[0][i] 1; dfs(board, 0, i,1); } for(int j 0; j m; j) { check1[j][0] 1; dfs(board,j ,0,1); } for(int i 0; i n; i) { check2[m-1][i] 1; dfs(board, m-1, i, 2); } for(int j 0; j m; j) { check2[j][n-1] 1; dfs(board, j, n - 1,2); } for (int i 0; i m; i) { for (int j 0; j n; j) { if (check1[i][j] check2[i][j]) { ret.push_back({i, j}); } } } return ret; } void dfs(vectorvectorint board, int x, int y, int z) { for(int k 0; k 4; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n board[i][j] board[x][y]) { if(z 1 check1[i][j] false) { check1[i][j] true; dfs(board,i,j,1); } else if(z 2 check2[i][j] false) { check2[i][j] true; dfs(board,i,j,2); } } } } };6.扫雷游戏529. 扫雷游戏 - 力扣LeetCode这题需要注意的点不多。第一就是某点周围有雷和无雷后续的情况是不同的第二就是遍历的时候注意已经走过的路不用再走即board[i][j] E时我们才继续class Solution { public: 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; vectorvectorchar updateBoard(vectorvectorchar board, vectorint 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(vectorvectorchar board, int x, int y) { int flag 0; for(int k 0; k 8; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n ) { if(board[i][j] M) { flag; } } } if(flag) { board[x][y] 0 flag; return ; } else { board[x][y] B; for(int k 0; k 8; k) { int i x dx[k]; int j y dy[k]; if(i 0 i m j 0 j n board[i][j] E) { dfs(board, i, j); } } } } };