当前位置：首页 > article >正文

【算法刷题指南】BFS解决FloodFill算法

article 2024/10/10 13:21:58

在这里插入图片描述

🌈个人主页：南桥几晴秋
🌈C++专栏：南桥谈C++
🌈C语言专栏： C语言学习系列
🌈Linux学习专栏：南桥谈Linux
🌈数据结构学习专栏：数据结构杂谈
🌈数据库学习专栏：南桥谈MySQL
🌈Qt学习专栏：南桥谈Qt
🌈菜鸡代码练习：练习随想记录
🌈git学习：南桥谈Git

🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈 本科在读菜鸡一枚，指出问题及时改正

文章目录

733.图像渲染
200. 岛屿数量
695.岛屿的最大面积
130.被围绕的区域

733.图像渲染

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.empty()) {
            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;
    }
};

200. 岛屿数量

200.岛屿数量

class Solution {
    int m, n;
    typedef pair<int, int> PII;
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};
    bool vis[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 (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<PII> 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 && !vis[x][y] &&
                    grid[x][y] == '1') {
                    q.push({x, y});
                    vis[x][y] = true;
                }
            }
        }
    }
};

695.岛屿的最大面积

class Solution {
    typedef pair<int, int> PII;
    int m, n;
    bool vis[55][55];
    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {1, -1, 0, 0};

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1 && !vis[i][j]) {
                    ans = max(ans, bfs(grid, i, j));
                }
            }
        }
        return ans;
    }

    int bfs(vector<vector<int>>& grid, int i, int j) {
        int cnt = 0;
        queue<PII> q;
        q.push({i, j});
        vis[i][j] = true;
        cnt++;

        while (!q.empty()) {
            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 && !vis[x][y] &&
                    grid[x][y] == 1) {
                    q.push({x, y});
                    vis[x][y] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }
};

130.被围绕的区域

class Solution {
    int m,n;
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    bool vis[205][205];
    typedef pair<int,int> PII;

public:
    void solve(vector<vector<char>>& board) {
        m=board.size(),n=board[0].size();
        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]=='.') board[i][j]='O';
            }
        }

    }

    void bfs(vector<vector<char>>& board,int i,int j)
    {
        queue<PII> q;
        q.push({i,j});
        board[i][j]='.';

        while(!q.empty())
        {
            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]='.';
                }
            }
        }
    }
};