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;}
};