2026/05/15

[LeetCode] 994 Rotting Oranges

BFS

 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
class State {
public:
  int x, y, depth;
};

class Solution {
private:
  int dirX[4] = {0, 1, 0, -1};
  int dirY[4] = {1, 0, -1, 0};

public:
  int orangesRotting(vector<vector<int>> &grid) {
    int N = grid.size();
    int M = grid[0].size();
    std::queue<State> Q;

    int fresh = 0;
    for (int i = 0; i < N; i++)
      for (int j = 0; j < M; j++)
        if (grid[i][j] == 1)
          fresh++;
        else if (grid[i][j] == 2)
          Q.push(State(i, j, 0));

    int maxDepth = 0;
    int rotten = 0;
    while (!Q.empty()) {
      State cur = Q.front();
      Q.pop();
      maxDepth = std::max(maxDepth, cur.depth);
      for (int i = 0; i < 4; i++) {
        int dx = cur.x + dirX[i];
        int dy = cur.y + dirY[i];
        if (dx >= 0 && dx < N && dy >= 0 && dy < M && grid[dx][dy] == 1) {
          grid[dx][dy] = 2;
          rotten++;
          Q.push(State(dx, dy, cur.depth + 1));
        }
      }
    }
    if (rotten == fresh)
      return maxDepth;
    return -1;
  }
};
Labels: