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 | class Status {
public:
int x, y, dis;
Status(int _x, int _y, int _dis) : x(_x), y(_y), dis(_dis) {}
};
class Solution {
private:
int N, M;
vector<vector<int>> dis;
int dirX[4] = {0, 1, 0, -1};
int dirY[4] = {1, 0, -1, 0};
public:
vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {
queue<Status> Q;
N = mat.size();
M = mat[0].size();
dis.resize(N);
for (int i = 0; i < N; i++) {
dis[i].resize(M);
for (int j = 0; j < M; j++) {
if (mat[i][j] == 0) {
Q.push(Status(i, j, 0));
dis[i][j] = 0;
} else
dis[i][j] = INT_MAX;
}
}
while (!Q.empty()) {
Status cur = Q.front();
Q.pop();
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)
continue;
if (dis[dx][dy] <= cur.dis + 1)
continue;
dis[dx][dy] = cur.dis + 1;
Q.push(Status(dx, dy, cur.dis + 1));
}
}
return dis;
}
};
|