dfs专题五：FloodFill算法

1.图像渲染

link:733. 图像渲染 - 力扣（LeetCode）

code

class Solution {
public:
    int prev;
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(image[sr][sc] == color) return image;
        prev = image[sr][sc];
        dfs(image, sr, sc, color);
        return image;
    }
    vector<int> dx = {0, 0, -1, 1};
    vector<int> dy = {1, -1, 0, 0};
    void dfs(vector<vector<int>>& image, int row, int col, int color)
    {
        printf("(%d, %d) ", row, col);
        image[row][col] = color;
        for(int i = 0; i < 4; i++)
        {
            int x = row + dx[i], y = col + dy[i];
            if(x < 0 || x >= image.size() || y < 0 || y >= image[0].size() ||
            image[x][y] != prev) continue;// image代替used
            dfs(image, x, y, color);
        }
    }
};

2.岛屿数量

link:200. 岛屿数量 - 力扣（LeetCode）

求连通块数量

code

class Solution {
public:
    int ans = 0;
    int numIslands(vector<vector<char>>& grid) {
        // dfs
        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(grid[i][j] == '1')
                {
                    dfs(i, j, grid);// dfs把（i， j)和与其相连的1都改为0
                    ans++;
                }
            }
        return ans;
    }
    vector<int> dx = {0, 0, 1, -1};
    vector<int> dy = {1, -1, 0, 0};
    void dfs(int row, int col, vector<vector<char>>& grid)
    {
        grid[row][col] = '0';
        for(int i = 0; i < 4; i++)
        {
            int x = row + dx[i], y = col + dy[i];
            if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() || grid[x][y] != '1') continue;
            dfs(x, y, grid);
        }
    }
};

3.岛屿的最大面积

link:695. 岛屿的最大面积 - 力扣（LeetCode）

code

class Solution {
public:
    int ans = 0;
    int path = 0;// 当前面积
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        // dfs
        for(int i = 0; i < grid.size(); i++)
            for(int j = 0; j < grid[0].size(); j++)
            {
                if(grid[i][j] == 1)
                {
                    path = 0;
                    dfs(i, j, grid);// dfs求出（i， j)连通图面积并置为0， 同时更新ans
                    // grid代替used
                }
            }
        return ans;
    }
    vector<int> dx = {0, 0, -1, 1};
    vector<int> dy = {1, -1, 0, 0};
    void dfs(int row, int col, vector<vector<int>>& grid)
    {
        printf("(%d, %d) path:%d, ans:%d\n", row, col, path, ans);
        grid[row][col] = 0;
        path++;
        ans = max(ans, path);// 不用非要最后更新ans
        for(int i = 0; i < 4; i++)
        {
            int x = row + dx[i], y = col + dy[i];
            if(x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size()
            || grid[x][y] != 1) continue;// 剪枝
            dfs(x, y, grid);
        }
    }
};

4.被围绕的区域

link:130. 被围绕的区域 - 力扣（LeetCode）

或者正难则反， 先把和边界相邻的连通图消灭，之后就可以不用判读地/正常地消灭剩下合法连通图了

code

class Solution {
public:
    bool used[205][205];
    vector<pair<int, int>> tmp;// tmp代替used记录本次连通图元素， 省去每次遍历和clear used
    bool flag = true;// 此连通图是否合法（没有挨着边界）
    void solve(vector<vector<char>>& board) {
        memset(used, false, sizeof used);
        for(int i = 0; i < board.size(); i++)
            for(int j = 0; j < board[0].size(); j++)
            {
                if(board[i][j] == 'O' && !used[i][j])
                {
                    flag = true;
                    tmp.clear();
                    dfs(i, j, board);// 如果(i,j)合法，dfs会修改board
                    if(flag)
                    {
                        for(auto[x, y]:tmp)
                        {
                            board[x][y] = 'X';
                        }
                    }
                }
            }
    }
    vector<int> dx = {0, 0, 1, -1};
    vector<int> dy = {1, -1, 0, 0};
    void dfs(int row, int col, vector<vector<char>>& board)
    {
        used[row][col] = true;// dfs内标记/处理used等
        tmp.push_back({row, col});
        for(int i = 0; i < 4; i++)
        {
            int x = row + dx[i], y = col + dy[i];
            if(x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) 
            {
                flag = false;
                continue;
            }
            if(used[x][y] || board[x][y] == 'X') continue;// 剪枝
            dfs(x, y, board);
        }
        // used[row][col] = false; // dfs内回溯
    }
};

5.太平洋大西洋水流问题

link:417. 太平洋大西洋水流问题 - 力扣（LeetCode）

tips:正难则反 ， 从大洋反向灌溉即可。 避免了重复计算，大大降低了时间复杂度

code

class Solution {
public:
    vector<vector<bool>> pacific;
    vector<vector<bool>> atlantic;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        pacific = vector<vector<bool>>(heights.size(), vector<bool>(heights[0].size(), false));
        atlantic = pacific;
        // pacific
        printf("1:\n");
        for(int i = 0; i < heights.size(); i++)
        {
            dfs(i, 0, heights, pacific);// 函数内标记
        }
        printf("2:\n");
        for(int i = 1; i < heights[0].size(); i++)
        {
            dfs(0, i, heights, pacific);
        }
        // atlantic
        for(int i = 0; i < atlantic.size(); i++)
        {
            dfs(i, heights[0].size()-1, heights, atlantic);
        }
        for(int i = 0; i < atlantic[0].size(); i++)
        {
            dfs(heights.size()-1, i, heights, atlantic);
        }
        // 寻找交点
        vector<vector<int>> ans;
        for(int i = 0; i < heights.size(); i++)
            for(int j = 0; j < heights[0].size(); j++)
            {
                if(pacific[i][j] && atlantic[i][j])
                {
                    ans.push_back({i, j});
                }
            }
        return ans;
    }

    vector<int> dx = {0, 0, 1, -1};
    vector<int> dy = {1, -1, 0, 0};
    void dfs(int row, int col, vector<vector<int>>& heights, vector<vector<bool>>& used)
    {
        if(row < 0 || row >= heights.size() || col < 0 || col >= heights[0].size() || used[row][col]) return;
        used[row][col] = true;// 函数内标记， 且不回溯
        for(int i = 0; i < 4; i++)
        {
            int x = row + dx[i], y = col + dy[i];
            if(x < 0 || x >= heights.size() || y < 0 || y >= heights[0].size()
            || used[x][y] || heights[row][col] > heights[x][y]) continue;
            dfs(x, y, heights, used);
        }
    }
};

6.扫雷

link:529. 扫雷游戏 - 力扣（LeetCode）

code

class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if(board[click[0]][click[1]] == 'M') 
        {
            board[click[0]][click[1]] = 'X';
            return board;
        }
        dfs(click[0], click[1], board);// 递归展开
        return board;
    }

    void dfs(int row, int col, vector<vector<char>>& board)
    {
        if(row < 0 || row >= board.size() || col < 0 || col >= board[0].size() || board[row][col] != 'E') return;
        
        int cnt = 0;// 相邻雷的数量
        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j++)
            {
                int x = row + i, y = col + j;
                if((i == 0 && j == 0) || x < 0 || x >= board.size() || y < 0 || y >= board[0].size()) continue;
                if(board[x][y] == 'M')cnt++;
            }
        if(cnt) 
        {
            board[row][col] = cnt + '0';
            return;
        }
        else
        {
            board[row][col] = 'B';
        }
        // 周围没有雷
        for(int i = -1; i <= 1; i++)
            for(int j = -1; j <= 1; j++)
            {
                if(i == 0 && j == 0) continue;
                int x = row + i, y = col + j;
                dfs(x, y, board);
            }
    }
};