Day20260312#

1
class Solution {
2
    int cnt;
3
    int dis[10][10];
4
    int dir_x[4] = {0, 1, 0, -1};
5
    int dir_y[4] = {1, 0, -1, 0};
6
public:
7
    int orangesRotting(vector<vector<int>>& grid) {
8
        queue<pair<int, int>>Q;
9
        memset(dis, -1, sizeof(dis));
10
        cnt = 0;
11
        int n = (int)grid.size(), m = (int)grid[0].size(), ans = 0;
12
        for (int i = 0; i < n; ++i) {
13
            for (int j = 0; j < m; ++j) {
14
                if (grid[i][j] == 2) {
15
                    Q.emplace(i, j);
16
                    dis[i][j] = 0;
17
                }
18
                else if (grid[i][j] == 1) {
19
                    cnt += 1;
20
                }
21
            }
22
        }
23
        while (!Q.empty()){
24
            auto [r, c] = Q.front();
25
            Q.pop();
26
            for (int i = 0; i < 4; ++i) {
27
                int tx = r + dir_x[i];
28
                int ty = c + dir_y[i];
29
                if (tx < 0|| tx >= n || ty < 0|| ty >= m || ~dis[tx][ty] || !grid[tx][ty]) {
30
                    continue;
31
                }
32
                dis[tx][ty] = dis[r][c] + 1;
33
                Q.emplace(tx, ty);
34
                if (grid[tx][ty] == 1) {
35
                    cnt -= 1;
36
                    ans = dis[tx][ty];
37
                    if (!cnt) {
38
                        break;
39
                    }
40
                }
41
            }
42
        }
43
        return cnt ? -1 : ans;
44
    }
45
};