LeetCode 994. 腐烂的橘子

798236606

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

BFS

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

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

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

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


        int r = grid.size(), c = grid[0].size();


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

                if (grid[i][j] == 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[p.x - 1][p.y] && grid[p.x - 1][p.y] == 1) turn_bad(p.x - 1, p.y);
                if (p.x < r - 1 && !vis[p.x + 1][p.y] && grid[p.x + 1][p.y] == 1) turn_bad(p.x + 1, p.y);
                if (p.y > 0     && !vis[p.x][p.y - 1] && grid[p.x][p.y - 1] == 1) turn_bad(p.x, p.y - 1);
                if (p.y < c - 1 && !vis[p.x][p.y + 1] && grid[p.x][p.y + 1] == 1) turn_bad(p.x, p.y + 1);
            }

            ++t;
        }      

        return -1;
    }
};