Eclipse插件 idea 常用快捷键 sqlite junit 抖音 uiviewcontroller nodejs教程视频 android项目实例 js事件绑定 mysql降序 abaqus是什么软件 时间戳java java上传图片 python相对路径怎么写 pythonfor循环 java队列 java实用教程 java基础编程 java线程停止 linuxshell 高效能人士的七个习惯下载 销售单软件 在线手册 迅雷去广告版 瑞兹技能 视频md5修改器 现代操作系统 jsp源代码 五子棋大师 战地2地图包下载 allowtransparency 骰子表情包 下拉框默认选中 熊猫头表情包制作 js压缩图片 软件编程软件 firework软件 python游戏ps竖排文字 数组对象去重 cdr调和工具怎么用
当前位置: 首页 > 学习教程  > 编程语言

Leetcode 994. 腐烂的橘子 (多源BFS)

2020/12/28 18:42:42 文章标签:

这是典型得多源BFS算法,从初始每个源出发,不断像外扩散即可,只需要在单源BFS得基础上,初始得时候将每个源放到队列就行了。证明得方法也很简单,假设开始要有一个虚拟得源头,与初始的所有源相连即可。 int d…

 

这是典型得多源BFS算法,从初始每个源出发,不断像外扩散即可,只需要在单源BFS得基础上,初始得时候将每个源放到队列就行了。证明得方法也很简单,假设开始要有一个虚拟得源头,与初始的所有源相连即可。

 

int dx[] = {0,1,-1,0};
int dy[] = {1,0,0,-1};
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> q;
        int fresh = 0, time = 0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==1) fresh++;
                else if(grid[i][j]==2) q.push({i,j});
            }
        }
        if(fresh==0) return 0;
        while(!q.empty()){
            int n = q.size();
            if(fresh==0) return time;
            for(int i=0;i<n;i++){
                int x = q.front().first;
                int y = q.front().second;
                q.pop();
                for(int j=0;j<4;j++){
                    int a = x + dx[j];
                    int b = y + dy[j];
                    if(a>=0&&a<grid.size()&&b>=0&&b<grid[0].size()&&grid[a][b]==1){
                        fresh--;
                        grid[a][b] = 2;
                        q.push({a,b});
                    }
                }
            }
            time++;
        }
        return -1;
    }
};

 

 


本文链接: http://www.dtmao.cc/news_show_550089.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?