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:
vector<vector<int>> floodFill(vector<vector<int>>& 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(vector<vector<int>>& 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(vector<vector<char>>& 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(vector<vector<char>>& 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(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(!visited[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)
{
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(vector<vector<char>>& 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(vector<vector<char>>& 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];
vector<vector<int>> ret;
public:
vector<vector<int>> pacificAtlantic(vector<vector<int>>& 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(vector<vector<int>>& 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:
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;
}
void dfs(vector<vector<char>>& 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;
}
};
原文地址：https://blog.csdn.net/m0_74317866/article/details/142986171
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！