首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 994. 腐烂的橘子(多源bfs)

LeetCode 994. 腐烂的橘子(多源bfs)

作者头像
Ch_Zaqdt
发布2020-03-06 15:00:36
6670
发布2020-03-06 15:00:36
举报
文章被收录于专栏:Zaqdt_ACMZaqdt_ACM

       这道题刚开始看错题了,看到了图片就以为是就是从(0, 0)那个点开始,而且只有一个,然后敲完交了就wa了,然后才发现可能刚开始坏橘子有多个,而且还可能存在不连通的情况,所以就考虑多源bfs,刚开始将所有的坏橘子都扔进队列,然后bfs搜索就好了,不是很难,但是我的代码可能不太好读懂,我设置了一个嵌套pair的队列,也就是封装了三个参数,前两个是坐标,后一个是需要的天数( (.first.first, .first.second)这个表示坐标,.second表示需要的天数),然后将这个扔到队列中跑就好了,因为我在跑的过程中直接将新鲜的橘子变为坏橘子了,所以就没有用标记数组。

AC代码:

class Solution {
public:
    typedef pair<int,int> p;
    typedef pair<pair<int,int>, int> P;
    queue<pair<pair<int,int>,int> > q;
    int dir[4][2] = {1,0, 0,1, -1,0, 0,-1};
    int bfs(vector<vector<int> >& g){
        int n = g.size();
        int m = g[0].size();
        int cnt = 0;
        int ans = 0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(g[i][j] == 2){
                    q.push(P(p(i, j), 0));
                }
                else if(g[i][j] == 1) cnt ++;
            }
        }
        while(!q.empty()){
            ans = max(ans, q.front().second);
            for(int i=0;i<4;i++){
                int x = q.front().first.first + dir[i][0];
                int y = q.front().first.second + dir[i][1];
                if(x >= 0 && y >= 0 && x < n && y < m && g[x][y] == 1){
                    g[x][y] = 2;
                    cnt --;
                    q.push(P(p(x, y), q.front().second + 1));
                }
                if(cnt == 0) break;
            }
            q.pop();
        }
        return cnt == 0 ? ans : -1;
    }
    int orangesRotting(vector<vector<int>>& g) {
        return bfs(g);
    }
};
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2020-03-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档