leet-code/0994-rotting-oranges.cpp at main · gabeknob/leet-code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        queue<pair<int,int>> qu;
        int minutes = -1;
        bool done = true;

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 2) qu.push({ i, j });
                if (grid[i][j] == 1) done = false;
            }
        }

        if (done) return 0;

        while (qu.size()) {
            int size = qu.size();
            for (int i = 0; i < size; i++) {
                auto [x, y] = qu.front();
                qu.pop();

                if (x > 0 && grid[x-1][y] == 1) {
                    grid[x-1][y] = 2;
                    qu.push({ x-1, y });
                }
                if (y > 0 && grid[x][y-1] == 1) {
                    grid[x][y-1] = 2;
                    qu.push({ x, y-1 });
                }
                if (x < grid.size() - 1 && grid[x+1][y] == 1) {
                    grid[x+1][y] = 2;
                    qu.push({ x+1, y });
                }
                if (y < grid[0].size() - 1 && grid[x][y+1] == 1) {
                    grid[x][y+1] = 2;
                    qu.push({ x, y+1 });
                }
            }
            minutes++;
        }

        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[i].size(); j++) {
                if (grid[i][j] == 1) return -1;
            }
        }

        return minutes;
    }
};