leetcode

0 class Solution {

1 int n, m;

2

3 bool valid(int x, int y) { return x >= 0 && x < n && y >= 0 && y < m; }

4

5 public:

6 int maxDistance(vector<vector<int>> &grid) {

7 n = grid.size(), m = grid[0].size();

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

9

10 for (int i = 0; i < n; i++) {

11 for (int j = 0; j < m; j++) {

12 if (grid[i][j]) {

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

14 grid[i][j] = 0;

15 } else

16 grid[i][j] = -1;

17 }

18 }

19 if (q.empty() || q.size() == n * m) return -1;

20

21 vector<int> offset_x{0, 0, 1, -1}, offset_y{1, -1, 0, 0};

22

23 int res = 0;

24 while (!q.empty()) {

25 auto [a, b] = q.front();

26 q.pop();

27 res = max(res, grid[a][b]);

28 for (int i = 0; i < 4; i++) {

29 int x = a + offset_x[i];

30 int y = b + offset_y[i];

31 if (!valid(x, y) || grid[x][y] >= 0) continue;

32 grid[x][y] = grid[a][b] + 1;

33 q.push({x, y});

34 }

35 }

36

37 return res;

38 }

39 };