leetcode

0 class Solution {

1 int m, n;

2 vector<pair<int, int>> offset = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

3

4 int valid(int sr, int sc) { return sr >= 0 && sr < m && sc >= 0 && sc < n; }

5

6 public:

7 vector<vector<int>> updateMatrix(vector<vector<int>> &mat) {

8 m = mat.size();

9 n = mat[0].size();

10

11 vector<vector<int>> res(m, vector<int>(n, INT_MAX));

12 queue<pair<int, int>> q;

13

14 for (int i = 0; i < m; i++) {

15 for (int j = 0; j < n; j++) {

16 if (mat[i][j] == 0) {

17 res[i][j] = 0;

18 q.push({i, j});

19 }

20 }

21 }

22

23 while (!q.empty()) {

24 auto [sr, sc] = q.front();

25 q.pop();

26 for (auto &p : offset) {

27 int nsr = sr + p.first;

28 int nsc = sc + p.second;

29 if (valid(nsr, nsc)) {

30 if (res[nsr][nsc] > res[sr][sc] + 1) {

31 res[nsr][nsc] = res[sr][sc] + 1;

32 q.push({nsr, nsc});

33 }

34 }

35 }

36 }

37

38 return res;

39 }

40 };