798236606 发表于 2020-3-4 12:49:57

LeetCode 994. 腐烂的橘子

本帖最后由 798236606 于 2020-3-5 10:12 编辑

传送门：https://leetcode-cn.com/problems/rotting-oranges/

BFS
class Solution {
public:
    struct Pos{
      int x, y;
    };

    int good = 0;
    bool vis = {false};
    queue<Pos> q;

    void turn_bad(int x, int y)
    {
      q.push({x, y});
      vis = true;   
      --good;   
    }

    int orangesRotting(vector<vector<int>>& grid) {


      int r = grid.size(), c = grid.size();


      for (int i = 0; i < r; ++i)
      {
            for (int j = 0; j < c; ++j)
            {
                if (grid == 2)
                {
                  q.push({i, j});
                  vis = true;
                }

                if (grid == 1) ++good;         
            }
      }

      if (!good) return 0;

      int t = 0;
      while (int k = q.size())
      {
            if (!good) return t;

            while (k--)
            {
                Pos p = q.front();
                q.pop();

                if (p.x > 0   && !vis && grid == 1) turn_bad(p.x - 1, p.y);
                if (p.x < r - 1 && !vis && grid == 1) turn_bad(p.x + 1, p.y);
                if (p.y > 0   && !vis && grid == 1) turn_bad(p.x, p.y - 1);
                if (p.y < c - 1 && !vis && grid == 1) turn_bad(p.x, p.y + 1);
            }

            ++t;
      }      

      return -1;
    }
};
页: [1]
查看完整版本: LeetCode 994. 腐烂的橘子