floodfille专题篇

目录

图像渲染

岛屿数量

岛屿的最大面积

被围绕的区域

太平洋大西洋水流问题

扫雷游戏

---

图像渲染

题目

思路

从所给位置出发进行上下左右四个方向符合值相等的位置进行深度优先遍历，如果值与所给位置的值相等，则将该位置的值修改为目标值，并且以该位置为起点继续进行符合要求的深度优先遍历。

代码

class Solution {
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    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];
        dfs(image,sr,sc,color);
        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(x>=0 && x<m && y>=0 && y<n && image[x][y]==prev)
                dfs(image,x,y,color);
        }
    }
};

岛屿数量

题目

思路

从头到尾扫描整个二维数组，当扫描到该位置的值为1时，对该位置进行上下左右四个方向的深度优先遍历，并把遍历过的点进行标记，直到不再满足条件为止，每当扫描整个二维数组的位置满足值为1且没有标记过，就对计数进行+1.

代码

class Solution {
public:
    void dfs(vector<vector<char>>& grid,vector<vector<bool>> &visited,int i,int j)
    {
        visited[i][j]=true;
 
        vector<int> v1={-1,1,0,0};
        vector<int> v2={0,0,-1,1};
 
        for(int k=0;k<4;k++)
        {
            int row=i+v1[k];
            int col=j+v2[k];
            if(row>=0 && row<grid.size() && col>=0 && col<grid[0].size()
            && grid[row][col]=='1' && !visited[row][col])
            {
                dfs(grid,visited,row,col);
            }
        }
    }
 
    int numIslands(vector<vector<char>>& grid) {
        int rows=grid.size();
        int cols=grid[0].size();
        vector<vector<bool>> visited(rows,vector<bool>(cols));
        int num=0;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(grid[i][j]=='1' && !visited[i][j])
                {
                    dfs(grid,visited,i,j);
                    num++;
                }
            }
        }
        return num;
    }
};

岛屿的最大面积

题目

思路

从头到尾扫描整个二维数组，每当该位置的值为1且没有被标记过，就对该位置进行深度优先遍历，直到不再满足条件为止，对本次递归得到的面积进行记录，取所以得到的面积的最大值。

代码

class Solution {
public:
    //深度优先遍历
    int getArea(vector<vector<int>>& grid,vector<vector<bool>>& visited,int i,int j)
    {
        visited[i][j]=true;
 
        vector<int> v1={-1,1,0,0};
        vector<int> v2={0,0,-1,1};
 
        int area=1;
        for(int k=0;k<4;k++)
        {
            int row=i+v1[k];
            int col=j+v2[k];
            if(row>=0 && row<grid.size() && col>=0 && col<grid[0].size()
            && grid[row][col]==1 && !visited[row][col])
            {
                area+=getArea(grid,visited,row,col);
            }
        }
 
        return area;
    }
 
    //广度优先遍历
    // int getArea(vector<vector<int>>& grid,vector<vector<bool>>& visited,int i,int j)
    // {
    //     queue<int> q1;
    //     queue<int> q2;
    //     q1.push(i);
    //     q2.push(j);
    //     visited[i][j]=true;
 
    //     vector<int> v1={-1,1,0,0};
    //     vector<int> v2={0,0,-1,1};
 
    //     int area=0;
    //     while(!q1.empty())
    //     {
    //         int r=q1.front();
    //         int c=q2.front();
    //         q1.pop();
    //         q2.pop();
    //         area++;
 
    //         for(int k=0;k<4;k++)
    //         {
    //             int row=r+v1[k];
    //             int col=c+v2[k];
    //             if(row>=0 && row<grid.size() && col>=0 && col<grid[0].size()
    //             && grid[row][col]==1 && !visited[row][col])
    //             {
    //                 q1.push(row);
    //                 q2.push(col);
    //                 visited[row][col]=true;
    //             }
    //         }
    //     }
 
    //     return area;
    // }
 
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int rows=grid.size();
        int cols=grid[0].size();
        vector<vector<bool>> visited(rows,vector<bool>(cols));
        int maxArea=0;
        for(int i=0;i<rows;i++)
        {
            for(int j=0;j<cols;j++)
            {
                if(grid[i][j]==1 && !visited[i][j])
                {
                    int area=getArea(grid,visited,i,j);
                    maxArea=max(maxArea,area);
                }
            }
        }
        return maxArea;
    }
};

被围绕的区域

题目

思路

如果这道题还用之前的方法是很难解决这道题的，因为碰到的位置的值为O的点可能并不是被包围的，因此我们可以尝试采用“正难则反”的思想，先找出来边界上是值为O的点，且对这些点进行深度优先遍历，将这些值为O的点的值置为字符‘*’,当对所有边界上值为O的点进行深度优先遍历过后，然后再扫描整个二维数组，把值为'*'的点的值修改为字符'X'，把值为'*'的点的值修改为'X'，返回修改后的二维数组即可。

代码

class Solution {
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
    int m,n;
public:
    void solve(vector<vector<char>>& 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]=='*') board[i][j]='O';
                else if(board[i][j]=='O') board[i][j]='X';
            }
        return;
    }
 
    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(x>=0 && x<m && y>=0 && y<n && board[x][y]=='O'){
                board[x][y]='*';
                dfs(board,x,y);
            }
        }
    }
};

太平洋大西洋水流问题

题目

思路

如果这道题通过扫描整个二维数组，然后对每个位置进行上下左右深度优先遍历，递归条件是该位置上下左右四个方向的值小于等于该位置的值，但是这样的话，似乎还是没有头绪，这时，我们不妨尝试和解决上一道题同样的思路，采用“正难则反”的思想，先遍历太平洋的两个边界上的位置，进行上下左右四个方向上的深度优先遍历，递归条件是该位置上下左右四个方向上的值大于等于该位置的值且没有被访问过，然后再遍历大西洋的两个边界上的位置，进行上下左右四个方向上的深度优先遍历，递归条件依旧是该位置上下左右四个方向上的值大于等于该位置的值且没有被访问过，最后遍历整个二维数组大小的两个二维标记数组，如果某个位置的值都为true的话，表明该位置可以同时流向太平洋和大西洋，把该位置加入到数组中，最后返回结果即可。

代码

class Solution {
    int m,n;
    int dx[4]={1,-1,0,0};
    int dy[4]={0,0,1,-1};
 
public:
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
        m=heights.size(),n=heights[0].size();
        vector<vector<bool>> pac(m,vector<bool>(n));
        vector<vector<bool>> atl(m,vector<bool>(n));
        for(int i=0;i<m;i++) dfs(heights,i,0,pac);
        for(int i=0;i<n;i++) dfs(heights,0,i,pac);
        for(int i=0;i<m;i++) dfs(heights,i,n-1,atl);
        for(int i=0;i<n;i++) dfs(heights,m-1,i,atl);
        vector<vector<int>> ret;
        for(int i=0;i<m;i++)
            for(int j=0;j<n;j++)
                if(pac[i][j] && atl[i][j])
                    ret.push_back({i,j});
        return ret;
    }
 
    void dfs(vector<vector<int>>& heights,int i,int j,vector<vector<bool>>& vv){
        vv[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 && !vv[x][y] && heights[x][y]>=heights[i][j]){
                dfs(heights,x,y,vv);
            }
        }
    }
};

扫雷游戏

题目

思路

这道题虽然题目比较长，文字描述较多，但是理解意思后其实是很简单的，下面依旧是使用深度优先遍历来解决，首先看一下点击位置是不是地雷，如果是的话，将该位置的值修改为‘X’并返回，如果不是地雷，对该位置进行深度优先遍历，首先统计该位置周围有多少个地雷，如果该位置周围有地雷，则将该位置的值修改为地雷个数，否则，对该位置继续进行深度优先遍历。

代码

class Solution {
    int dx[8]={1,-1,0,0,1,1,-1,-1};
    int dy[8]={0,0,1,-1,1,-1,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(x>=0 && x<m && y>=0 && y<n && board[x][y]=='M')
                count++;
        }
        if(count)
            board[i][j]=count+'0';
        else{
            board[i][j]='B';
            for(int k=0;k<8;k++){
                int x=i+dx[k],y=j+dy[k];
                if(x>=0 && x<m && y>=0 && y<n && board[x][y]=='E')
                    dfs(board,x,y);
            }
        }
    }
};