【算法】bfs解决FloodFill问题

个人主页 ： zxctscl
如有转载请先通知

FloodFill算法

FloodFill就是洪水灌溉，解决的就是下面这样一种模型。
解决性质相同的联通块问题，用的方法就是dfs深度优先搜索遍历：一条道走到黑，直到不能再走，不能再走就倒回去；或者是bfs宽度优先搜索遍历：一层一层剥开

1. 733. 图像渲染

1.1 分析

用bfs模拟流程
假设有这么一个矩阵，给的位置是(1,1）与（1，1）相连的所有像素相同的点，全部修改为2。
那么就一层一层搜索，就是从(1,1）开始搜索：
第一层从(1,1）开始的上下左右扫描，把(1,2)和（2,1）的值都修改为2；
第二层从(1,2)和（2,1）开始：（1,2）的扫描多加了（0,2）；
（2,1）的扫描多了（2,0）和（3,1）
第三层从（0,2）、（2,0）和（3,1）开始：（0,2）多加了（0,3）；（2,0）没有；（3,1）多了（3,2）
第四层从（0,3）、（3,2）发现没有了，层序遍历就完成了。

1.2 代码

class Solution {
    typedef pair<int,int> PII;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) 
    {
        int m=image.size(),n=image[0].size();
        int prev=image[sr][sc];//标记一下需要修改的像素值
        if(prev==color)return image;//处理边界情况
       
        queue<PII> q;
        q.push({sr,sc});

        while(q.size())
        {
            auto [a,b]=q.front();//取出对头
            q.pop();
            image[a][b]=color;
            for(int i=0;i<4;i++)
            {
                int x=a+dx[i],y=b+dy[i];
                if(x>=0&&x<m&&y>=0&&y<n&&image[x][y]==prev)
                {
                    q.push({x,y});
                }
            }
        }
        return image;

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

2. 200. 岛屿数量

2.1 分析

模拟一下过程
以例2模拟：从（0,0）位置开始扩展，不能扩展回去，为了不在原数组上面修改，可以给一个bool数组和原矩阵规模是一样的，然后里面如果存false，就代表这个位置没有遍历过，如果存true表示遍历过。那么从这个位置开始它的上下左右中如果有true，那么就不扫描。

2.2 代码

class Solution {
    int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };  
    bool vis[301][301];
    int m,n;
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(grid[i][j]=='1'&&!vis[i][j])
                {
                    ret++;
                    bfs(grid,i,j);
                }
            }
        }
        return ret;
    }
    void bfs(vector<vector<char>>&grid,int i,int j)
    {
        queue<pair<int,int>>q;
        q.push({i,j});
        vis[i][j]=true;

        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();
            for(int k=0;k<4;k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y]=='1'&&!vis[x][y])
                {
                    q.push({ x,y });
                    vis[x][y]=true;
                }
            }
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

3. 695. 岛屿的最大面积

3.1 分析

和上面那题类似，就加了一个在dfs里面统计一下面积，然后再返回的这些面积里面找到最大的那个就行。

3.2 代码

class Solution {
     int dx[4] = { 0,0,1,-1 };
    int dy[4] = { 1,-1,0,0 };
    bool vis[51][51];
    int m, n;
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 (grid[i][j] == 1 && !vis[i][j])
                {
                    
                   ret=max(ret, bfs(grid, i, j));
                }
            }
        }
        return ret;
    }
    int bfs(vector<vector<int>>& grid, int i, int j)
    {
        queue<pair<int, int>>q;
        q.push({ i,j });
        vis[i][j] = true;
        int count = 1;
        while (q.size())
        {
            auto [a, b] = q.front();
            q.pop();
            for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
                {
                    q.push({ x,y });
                    vis[x][y] = true;
                    count++;
                }
            }
        }
        return count;
    }
    
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

4. 130. 被围绕的区域

4.1 分析

如果直接开始模拟，那么与边缘相关的联通块就不好做。那么就从与边缘相关的连通块开始做，先遍历四条变，如果边上有0，就先对它们来一个层序遍历，然后把这些位置全部修改为无关的字符。那么接下来就只需要遍历矩阵，把里面的0都修改为x就可以，因为没有被包围的四边已经处理了，剩下的就是一定被包围的。最后在把无关的字符再改回去就可以了。
这个方法叫正难则反，先处理边界上0，改为.，再扫描完矩阵后，还原。

4.2 代码

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();
        //先处理边界o，把他们修改为a
        for(int j=0;j<n;j++)
        {
            if(board[0][j]=='O')bfs(board,0,j);
             if(board[m-1][j]=='O')bfs(board,m-1,j);
        }

          for(int i=0;i<m;i++)
          {
            if(board[i][0]=='O')bfs(board,i,0);
            if(board[i][n-1]=='O')bfs(board,i,n-1);
          }


          for(int i=0;i<m;i++)
          {
            for(int j=0;j<n;j++)
                if(board[i][j]=='O')board[i][j]='X';
                else if(board[i][j]=='a')board[i][j]='O';
          }
         
    }

    void bfs(vector<vector<char>>& board,int i,int j)
    {
        queue<pair<int, int>>q;
        q.push({ i,j });
        board[i][j]='a';
        while(q.size())
        {
            auto [a,b]=q.front();
            q.pop();
             for (int k = 0; k < 4; k++)
            {
                int x = a + dx[k], y = b + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O' )
                {
                    q.push({ x,y });
                    board[x][y] = 'a';
                   
                }
            }
        }
    }

};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

有问题请指出，大家一起进步吧！！！