品牌网站建设费用,网站开发设计运维,投资建设网站,合肥建设学校网站首页文章目录 FloodFill 算法#xff08;DFS#xff09;图像渲染岛屿数量岛屿的最大面积被围绕的区域太平洋大西洋水流问题扫雷游戏衣橱整理 FloodFill 算法#xff08;DFS#xff09; 漫水填充(Flood Fi)算法是一种图像处理算法#xff0c;在计算机图形学和计算机视觉中被广泛… 文章目录 FloodFill 算法DFS图像渲染岛屿数量岛屿的最大面积被围绕的区域太平洋大西洋水流问题扫雷游戏衣橱整理 FloodFill 算法DFS 漫水填充(Flood Fi)算法是一种图像处理算法在计算机图形学和计算机视觉中被广泛应用。它用于填充图像中的连通区域从一个种子点开始沿着相邻的像素进行填充操作直到达到某个停止条件为止。该算法可以实现图像填充、颜色替换、图像分割等操作。 图像渲染 题目图像渲染 思路 从起点开始深度优先搜索当遇到上下左右和当前一样时即为合法目标将其修改为color用一个标记数组visited来判断当前位置是否访问过 C代码
class Solution
{bool visited[51][51];int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0}; int m, n;int prev;
public:vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) {if(image[sr][sc] color) return image;m image.size(), n image[0].size();prev image[sr][sc];visited[sr][sc] true;dfs(image, sr, sc, color);visited[sr][sc] false;return image;}void dfs(vectorvectorint image, int i, int j, int color){image[i][j] color;for(int k 0; k 4; k){int x i dx[k], y j dy[k];if(0 x x m 0 y y n !visited[x][y] image[x][y] prev){visited[x][y] true;dfs(image, x, y, color);visited[x][y] false;}}}
};岛屿数量 题目岛屿数量 思路 遍历数组找到1开始搜索搜索一次答案遍历过后用一个标记数组visited标记该位置 C代码
class Solution
{int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m, n;bool visited[301][301];
public:int numIslands(vectorvectorchar 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(!visited[i][j] grid[i][j] 1){ret;dfs(grid, i, j);}}return ret;}void dfs(vectorvectorchar grid, int i, int j){visited[i][j] true;for(int k 0; k 4; k){int x i dx[k], y j dy[k];if(0 x x m 0 y y n !visited[x][y] grid[x][y] 1){dfs(grid, x, y);}}}
};岛屿的最大面积 题目岛屿的最大面积 思路 和岛屿数量解题思路一样只不过在每次遍历岛屿的时候用一个变量count来统计当前岛屿的大小并变量完当前岛屿后和之前最大的结果ret取一个最大值 C代码
class Solution
{bool visited[51][51];int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m, n;int count;
public: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(!visited[i][j] grid[i][j] 1){count 0;dfs(grid, i, j);ret max(ret, count);}return ret;}void dfs(vectorvectorint grid, int i, int j){visited[i][j] true;count;for(int k 0; k 4; k){int x i dx[k], y j dy[k];if(0 x x m 0 y y n !visited[x][y] grid[x][y] 1){dfs(grid, x, y);}}}
};被围绕的区域 题目被围绕的区域 思路 和岛屿数量解题思路一样只不过在每次遍历岛屿的时候用一个变量count来统计当前岛屿的大小并变量完当前岛屿后和之前最大的结果ret取一个最大值 C代码
class Solution
{int dx[4] {0,0,1,-1};int dy[4] {-1,1,0,0};int m, n;
public:void solve(vectorvectorchar 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 i 1; i n - 1; 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)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(vectorvectorchar board, int i, int j){board[i][j] .;for(int k 0; k 4; k){int x i dx[k], y j dy[k];if(0 x x m 0 y y n board[x][y] O){dfs(board, x, y);}}}
};太平洋大西洋水流问题 题目太平洋大西洋水流问题 思路
对于太平洋边界即第一行和第一列上的每个单元格将其标记为可达太平洋toPO true并将其加入队列进行DFS。在DFS过程中如果当前单元格的相邻单元格高度不低于当前单元格且未被标记为可达太平洋则将其标记为可达太平洋并加入队列继续搜索对于大西洋边界即最后一行和最后一列上的每个单元格进行类似的操作将其标记为可达大西洋toAO true遍历整个矩阵对于每个单元格如果它同时被标记为可达太平洋和可达大西洋toPO toAO则将其坐标加入结果列表。
C代码
class Solution
{int dx[4] {0, 0, 1, -1};int dy[4] {1, -1, 0, 0};int m, n;bool toPO[201][201];bool toAO[201][201];vectorvectorint ret;
public:vectorvectorint pacificAtlantic(vectorvectorint heights) {m heights.size(), n heights[0].size();// 左、上for(int i 0; i m; i) dfs(heights, i, 0, toPO);for(int i 0; i n; i) dfs(heights, 0, i, toPO);// 右、下for(int i 0; i m; i) dfs(heights, i, n - 1, toAO);for(int i 0; i n; i) dfs(heights, m - 1, i, toAO);for(int i 0; i m; i)for(int j 0; j n; j)if(toPO[i][j] toAO[i][j]) ret.push_back({i, j});return ret;}void dfs(vectorvectorint heights, int i, int j, bool visited[201][201]){visited[i][j] true;for(int k 0; k 4; k){int x i dx[k], y j dy[k];if(0 x x m 0 y y n !visited[x][y] heights[x][y] heights[i][j])dfs(heights, x, y, visited);}}
};扫雷游戏 题目扫雷游戏 思路 理解题目意思模拟深度优先搜索 C代码
class Solution
{int dx[8] {0, 0, 1, 1, 1, -1, -1, -1};int dy[8] {1, -1, 0, 1, -1, 0, 1, -1};int m, n;
public: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;}void dfs(vectorvectorchar board, int i, int j){// 统计周围地雷个数int count 0;for(int k 0; k 8; k){int x i dx[k], y j dy[k];if(0 x x m 0 y 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 i dx[k], y j dy[k];if(0 x x m 0 y y n board[x][y] E){dfs(board, x, y);}} }}
};衣橱整理 题目衣橱整理 思路 模拟DFS C代码
class Solution
{int ret;bool vis[101][101];int dx[4] {0, 1};int dy[4] {1, 0};int m, n, cnt;
public:int wardrobeFinishing(int _m, int _n, int _cnt) {m _m, n _n, cnt _cnt;dfs(0, 0);return ret;}void dfs(int i, int j){ret;vis[i][j] true;for(int k 0; k 4; k){int x i dx[k], y j dy[k];if(x 0 x m y 0 y n !vis[x][y] check(x,y)){dfs(x, y);}}}bool check(int i,int j){int tmp 0;while(i){tmp i % 10;i / 10;}while(j){tmp j % 10;j / 10;}return tmp cnt;}
};
