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

BFS-专题

article 2024/12/24 11:43:36

目录

1.FloodFill

1.1图像渲染

2.岛屿数量

3.岛屿的最大数量

4.被围绕的区域

2.最短路

 2.1迷宫中离入口最近的出口

2最小基因变化

3.单词接龙1

4.为高尔夫比赛砍树

3.多源最短路

1. 矩阵

2.飞地的数量

3.地图中的最高点

4.地图分析

1.FloodFill

1.1图像渲染

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

本题思路很清晰，就是从当前位置开始，向四周遍历.

唯一要注意的是，如果初始位置的像素值已经等于color了，就直接返回，不然会死循环

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;
    struct kp{
        int x,y;
    };
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n)return false;
        return true;
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        m=image.size(),n=image[0].size();
        int initcolor=image[sr][sc];
        if(initcolor==color)return image;
        queue<kp>mp;
        mp.push({sr,sc});
        image[sr][sc]=color;
        while(mp.size()>0)
        {
            auto tmp=mp.front();
            mp.pop();
            for(int i=0;i<4;i++)
            {
                int nx=tmp.x+dx[i],ny=tmp.y+dy[i];
                if(check(nx,ny)&&image[nx][ny]==initcolor)
                {
                    image[nx][ny]=color;
                    mp.push({nx,ny});
                }
            }
        }
        return image;
    }
};

2.岛屿数量

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

记得把while里面的i看作另一个i，这里写得不严谨

class Solution {
public:
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n||(*flag)[x][y])return false;
        return true;
    }
    int numIslands(vector<vector<char>>& grid) {
        m=grid.size();
        n=grid[0].size();
        flag=new vector<vector<bool>>(m,vector<bool>(n,false));
        queue<pair<int,int>>mp;
        int ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]=='1'&&(*flag)[i][j]==false)
                {
                    mp.push({i,j});
                    ans++;
                    (*flag)[i][j]=true;
                    while(mp.size()>0)
                    {
                        auto [x,y]=mp.front();
                        mp.pop();
                        for(int i=0;i<4;i++)
                        {
                            int nx=x+dx[i],ny=y+dy[i];
                            if(check(nx,ny)&&grid[nx][ny]=='1')
                            {
                                (*flag)[nx][ny]=true;
                                mp.push({nx,ny});
                            }
                        }
                    }
                }
            }
        }
        return ans;
    }
    vector<vector<bool>>*flag;
    int m,n;
};

3.岛屿的最大数量

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

class Solution {
public:
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n||(*flag)[x][y])return false;
        return true;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        flag=new vector<vector<bool>>(m,vector<bool>(n,false));
        int ans=0;
        queue<pair<int,int>>mp;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1&&(*flag)[i][j]==false)
                {
                    int res=1;
                    mp.push({i,j});
                    (*flag)[i][j]=true;
                    while(mp.size()>0)
                    {
                        auto [x,y]=mp.front();
                        
                        mp.pop();
                        for(int k=0;k<4;k++)
                        {
                            int nx=x+dx[k],ny=y+dy[k];
                            if(check(nx,ny)&&grid[nx][ny]==1)
                            {
                                res++;
                                (*flag)[nx][ny]=true;
                                mp.push({nx,ny});
                            }
                        }
                    }
                    ans=max(ans,res);
                }
            }
        }
        return ans;
    }
    int m,n;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    vector<vector<bool>>*flag;
};

4.被围绕的区域

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

这题不是死找，要先把四周一圈处理下。让边缘的O及其连接的O全部先处理成#号。

然后再遍历整个地图，#号修改成O，O修改成X

class Solution {
public:
    bool check(int x, int y) {
        if (x < 0 || x >= m || y < 0 || y >= n )
            return false;
        return true;
    }
    void bfs(vector<vector<char>>& board, int i, int j) {
        queue<pair<int, int>> mp;
        mp.push({i, j});
        board[i][j] = '#';
        while (mp.size() > 0) {
            auto [x, y] = mp.front();
            mp.pop();
            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k], ny = y + dy[k];
                if (check(nx, ny) && board[nx][ny] == 'O') {
                    mp.push({nx, ny});
                    board[nx][ny] = '#';
                }
            }
        }
    }
    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')bfs(board, i, 0);
            if(board[i][n-1]=='O')bfs(board, i, n-1);
        }
        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++) {
            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';
            }
        }
    }
    int m, n;
    int dx[4] = {0, 0, -1, 1}, dy[4] = {1, -1, 0, 0};
};

2.最短路

 2.1迷宫中离入口最近的出口

1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

思路就是bfs找最短路

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;
    vector<vector<bool>>*vis;
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n||(*vis)[x][y])return false;
        return true;
    }
    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        m=maze.size();
        n=maze[0].size();
        vis=new vector<vector<bool>>(m,vector<bool>(n,false));
        int sx=entrance[0],sy=entrance[1];
        queue<pair<int,int>>mp;
        mp.push({sx,sy});
        (*vis)[sx][sy]=true;
        int step=0;
        while(mp.size())
        {
            step++;
            int sz=mp.size();
            while(sz--)
            {
                auto [x,y]=mp.front();
                mp.pop();
                for(int i=0;i<4;i++)
                {
                    int nx=x+dx[i],ny=y+dy[i];
                    if(check(nx,ny)&&maze[nx][ny]=='.')
                    {
                        if(nx==0||nx==m-1||ny==0||ny==n-1)
                        {
                            return step;
                        }
                        mp.push({nx,ny});
                        (*vis)[nx][ny]=true;
                    }
                }
            }
        }
        
        return -1;
    }

};

2最小基因变化

433. 最小基因变化 - 力扣（LeetCode）

class Solution {
public:
    vector<bool>*vis;
    int m;
    bool check(string &a,string &b)
    {
        int cnt=0;
        for(int i=0;i<8;i++)
        {
            if(a[i]!=b[i])cnt++;
            if(cnt>1)return false;
        }
        return true;
    }
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        if(startGene==endGene)return 0;
        if(bank.size()==0)return -1;
        m=bank.size();
        vis=new vector<bool>(m,false);
        queue<string>mp;
        mp.push(startGene);
        int step=0;
        while(mp.size())
        {
            step++;
            int sz=mp.size();
            while(sz--)
            {
                auto tmp=mp.front();
                mp.pop();
                for(int i=0;i<m;i++)
                {
                    if((*vis)[i]==false&&tmp!=bank[i]&&check(tmp,bank[i]))
                    {
                        (*vis)[i]=true;
                        mp.push(bank[i]);
                        if(bank[i]==endGene)
                        {
                            return step;
                        }
                    }
                }
            }
        }
        return -1;
    }
};

3.单词接龙1

127. 单词接龙 - 力扣（LeetCode）

因为数据量不大，所以我先是写了个暴力BFS，然后是卡着点过的，时间复杂度很高。

version1:

class Solution {
public:
    bool check(string a,string b)
    {
        int cnt=0;
        for(int i=0;i<a.size();i++)
        {
            if(a[i]!=b[i])cnt++;
            if(cnt>=2)return false;
        }
        return true;
    }
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(beginWord==endWord)return 2;
        if(wordList.size()==0)return 0;
        int m=wordList.size();
        vis=new vector<bool>(m,false);
        queue<string>mp;
        mp.push(beginWord);
        int step=1;
        while(mp.size()>0)
        {
            step++;
            int sz=mp.size();
            while(sz--)
            {
                auto tmp=mp.front();
                mp.pop();
                for(int i=0;i<m;i++)
                {
                    if((*vis)[i]==false&&tmp!=wordList[i]&&check(tmp,wordList[i]))
                    {
                        if(wordList[i]==endWord)return step;
                        (*vis)[i]=true;
                        mp.push(wordList[i]);
                    }
                }
            }
        }
        return 0;
    }
    vector<bool>*vis;
};

version2:

主要是修改了判断条件，不再用暴力判断，而是利用map和set，快速判断。

class Solution {
public:
    int ladderLength(string beginWord, string endWord,
                     vector<string>& wordList) {
        unordered_set<string> hash1(wordList.begin(), wordList.end());
        if(hash1.find(endWord)==hash1.end())return 0;
        queue<string> mp;
        unordered_map<string,int>vis;
        mp.push(beginWord);
        vis[beginWord]=1;
        int step = 1;
        while (mp.size() > 0) {
            int sz = mp.size();
            step++;
            while (sz--) {
                auto tmp = mp.front();
                mp.pop();
                int m = tmp.size();
                for (int i = 0; i < m; i++) {
                    for (char j = 'a'; j <= 'z'; j++) {
                        if (tmp[i] == j)
                            continue;
                        char t = tmp[i];
                        tmp[i] = j;
                        if (tmp == endWord)
                            return step;
                        if (hash1.find(tmp)!=hash1.end()&&vis[tmp]==0) {
                            mp.push(tmp);
                            hash1.insert(tmp);
                            vis[tmp]=1;
                        }
                        tmp[i]=t;
                    }
                }
            }
        }
        return 0;
    }
};

4.为高尔夫比赛砍树

675. 为高尔夫比赛砍树 - 力扣（LeetCode）

一开始，我想着一次性完成，然后发现实现不了，于是把整个bfs，分成多个bfs。

class Solution {
public:
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    int m,n;
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n)return false;
        return true;
    }
    class kp{
    public:
        kp(int _x=0,int _y=0,int _index=0)
        {
            x=_x,y=_y,index=_index;
        }
        int x=0, y=0, index=-1;
    };
    bool vis[51][51];
    int bfs1(int sx,int sy,int c,vector<vector<int>>& forest){
        memset(vis,0,sizeof vis);
        queue<pair<int,int>>mp;
        mp.push({sx,sy});
        vis[sx][sy]=true;
        int step=0;
        if(forest[sx][sy]==c)return 0;
        while(mp.size()>0)
        {
            step++;
            int sz=mp.size();
            while(sz--)
            {
                auto [x,y]=mp.front();
                mp.pop();
                for(int i=0;i<4;i++)
                {
                    int nx=x+dx[i],ny=y+dy[i];
                    if(check(nx,ny)&&vis[nx][ny]==false&&forest[nx][ny]!=0)
                    {
                        vis[nx][ny]=true;
                        mp.push({nx,ny});
                        if(forest[nx][ny]==c)
                        {
                            bx=nx,by=ny;
                            forest[nx][ny]=1;
                            return step;
                        }
                    }
                }
            }
        }
        return -1;
    }
    int cutOffTree(vector<vector<int>>& forest) {
        m=forest.size();n=forest[0].size();
        int ans=0;
        set<int>value;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(forest[i][j]!=1&&forest[i][j]!=0)
                {
                    value.insert(forest[i][j]);
                }
            }
        }
        for (auto &e:value)
        {
            int p=bfs1(bx,by,e,forest);
            if(p==-1)return -1;
            else ans+=p;
        }
        return ans;
    }
    int bx=0,by=0;
};

3.多源最短路

1. 矩阵

542. 01 矩阵 - 力扣（LeetCode）

version1----写法跟之前的单源差不多，只是把每个起点一起放进去。同时本题要正难则反，所以是把0放进去

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        queue<pair<int,int>>mp;
        m=mat.size(),n=mat[0].size();
        vector<vector<int>>ret(m,vector<int>(n,0));
        vector<vector<bool>>vis(m,vector<bool>(n,false));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]==0)
                {
                    mp.push({i,j});
                    vis[i][j]=true;
                }
            }
        }
        int step=0;
        while(mp.size())
        {
            step++;
            int sz=mp.size();
            for(int i=0;i<sz;i++)
            {
                auto [x,y]=mp.front();
                mp.pop();
                for(int j=0;j<4;j++)
                {
                    int nx=x+dx[j],ny=y+dy[j];
                    if(check(nx,ny)&&vis[nx][ny]==false)
                    {
                        if(mat[nx][ny]==1)ret[nx][ny]=step;
                        vis[nx][ny]=true;
                        mp.push({nx,ny});
                    }
                }
            }
        }
        return ret;
    }
    int m,n;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n)return false;
        return true;
    }
};

注意，本题不能直接用静态数组开vis，因为会栈溢出

version2----是没有太多变量，while循坏比较简洁的写法

class Solution {
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        queue<pair<int,int>>mp;
        m=mat.size(),n=mat[0].size();
        vector<vector<int>>dist(m,vector<int>(n,-1));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]==0)
                {
                    mp.push({i,j});
                    dist[i][j]=0;
                }
            }
        }
        while(mp.size())
        {
            auto [x,y]=mp.front();
            mp.pop();
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i],ny=y+dy[i];
                if(check(nx,ny)&&dist[nx][ny]==-1)
                {
                    dist[nx][ny]=dist[x][y]+1;
                    mp.push({nx,ny});
                }
            }
        }
        return dist;
    }
    int m,n;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
    bool check(int x,int y)
    {
        if(x<0||x>=m||y<0||y>=n)return false;
        return true;
    }
};

2.飞地的数量

1020. 飞地的数量 - 力扣（LeetCode）

思路是正难则反，我们可以从边界的1开始遍历bfs，把边界的1都丢进队列中。

然后通过bfs，把跟边界1相连的连通块（值都为1的），全部设置为0。

最后遍历下原始地图，然后统计1的个数即可。

class Solution {
public:
    void bfs(vector<vector<int>>& grid)
    {
        queue<pair<int,int>>mp;
        for(int i=0;i<n;i++)
        {
            if(grid[0][i]==1)
            {
                mp.push({0,i});
            }
            if(grid[m-1][i]==1)
            {
                mp.push({m-1,i});
            }
        }
        for(int i=0;i<m;i++)
        {
            if(grid[i][0]==1)
            {
                mp.push({i,0});
            }
            if(grid[i][n-1]==1)
            {
                mp.push({i,n-1});
            }
        }
        while(mp.size())
        {
            auto [x,y]=mp.front();
            mp.pop();
            grid[x][y]=0;
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i],ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&grid[nx][ny]==1)
                {
                    mp.push({nx,ny});
                    grid[nx][ny]=0;
                }
            }
        }
    }
    int numEnclaves(vector<vector<int>>& grid) {
        m=grid.size();
        n=grid[0].size();
        bfs(grid);
        int ans=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    ans++;
                }
            }
        }
        return ans;
    }
    int m,n;
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
};

注意，可以设置vis数组标记有没有搜过，但本题不需要返回原始地图，所以我们直接修改1为0即可。

3.地图中的最高点

1765. 地图中的最高点 - 力扣（LeetCode）

思路就是从把水域全部加到队列。然后bfs找陆地连通块，设置高度为当前+1（贪心思想）

class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int m=isWater.size(),n=isWater[0].size();
        queue<pair<int,int>>mp;
        vector<vector<bool>>vis(m,vector<bool>(n,false));
        vector<vector<int>>ret(m,vector<int>(n,0));
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(isWater[i][j]==1)
                {
                    mp.push({i,j});
                    vis[i][j]=true;
                }
            }
        }
        while(mp.size())
        {
            auto [x,y]=mp.front();
            mp.pop();
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i],ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&vis[nx][ny]==false&&isWater[nx][ny]==0)
                {
                    ret[nx][ny]=ret[x][y]+1;
                    mp.push({nx,ny});
                    vis[nx][ny]=true;
                }
            }
        }
        return ret;
    }
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
};

4.地图分析

1162. 地图分析 - 力扣（LeetCode）

思路就是把陆地丢入队列，然后向外遍历，每次+1，同时更新答案。

class Solution {
public:
    int maxDistance(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        vector<vector<int>>dist(m,vector<int>(n,-1));
        queue<pair<int,int>>mp;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(grid[i][j]==1)
                {
                    mp.push({i,j});
                    dist[i][j]=0;
                }
            }
        }
        if(mp.size()==0||mp.size()==m*n)return -1;
        int ans=0;
        while(mp.size())
        {
            auto [x,y]=mp.front();
            mp.pop();
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i],ny=y+dy[i];
                if(nx>=0&&nx<m&&ny>=0&&ny<n&&dist[nx][ny]==-1)
                {
                    mp.push({nx,ny});
                    dist[nx][ny]=dist[x][y]+1;
                    ans=max(ans,dist[nx][ny]);
                }
            }
        }
        return ans;
    }
    int dx[4]={0,0,-1,1};
    int dy[4]={1,-1,0,0};
};


http://www.kler.cn/a/381017.html

相关文章：

  • Asp.Net FrameWork 4.7.2 WebAPI 使用WebSocket协议
  • echarts画风向杆
  • c# 实现一个简单的异常日志记录（异常迭代+分片+定时清理）+AOP Rougamo全局注入
  • ruoyi 请求参数类型不匹配，参数[giftId]要求类型为：‘java.lang.Long‘，但输入值为：‘orderGiftUnionList
  • 【day11】面向对象编程进阶（继承）
  • Unity全局雾效
  • 【Python】Python自习课：第一个python程序
  • GPT原理；ChatGPT 等类似的问答系统工作流程如下；当用户向 ChatGPT 输入一个问题后：举例说明；ChatGPT不是通过索引搜索的传统知识库
  • C++ explicit 关键字
  • 基于Arcpy和MATLAB批量提取指定经纬度点的栅格数据并转换为矩阵格式
  • 计算机系统结构为什么用architecture 而不是structure?
  • redis：set集合命令，内部编码，使用场景
  • 软件测试学习笔记丨Vue常用指令-条件渲染（v-if）
  • 矩阵NFC碰一碰发视频源码开发技术解析，支持OEM
  • ‌Vue 3相比Vue 2的主要改进‌?
  • SQL server 中 CROSS APPLY的使用
  • SpringBoot+Shiro权限管理
  • 【机器学习】24. 聚类-层次式 Hierarchical Clustering
  • Android Studio 多工程公用module引用
  • 【专属情侣空间】不懂技术，不懂代码，你也可以拥有专属的情侣空间了
  • 各主流编程语言的常见问题点（不定时更新）
  • FrankenPHP实践
  • spring-boot（更换数据源）
  • clickhouse运维篇（二）：多机器手动部署ck集群
  • 一篇文章帮你彻底解决gradle、gradle插件、jdk版本兼容性问题
  • 洗衣小程序/洗鞋小程序 洗衣店系统，洗衣系统源码