leetcode

0 class Solution {

1 public:

2 int maximumSafenessFactor(vector<vector<int>> &grid) {

3 static int offset[] = {-1, 0, 1, 0, -1};

4 const int n = size(grid);

5

6 using qtype_t = tuple<int, int>;

7 queue<qtype_t> q;

8

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

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

11 if (grid[i][j] != 1) continue;

12 q.emplace(i, j);

13 }

14 }

15

16 for (int lvl = 2; !q.empty(); lvl++) {

17 for (int k = q.size(); k > 0; k--) {

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

19 q.pop();

20

21 for (int k = 0; k < 4; k++) {

22 const int x = a + offset[k + 1];

23 const int y = b + offset[k];

24

25 if (x < 0 || x >= n || y < 0 || y >= n) continue;

26 if (grid[x][y]) continue;

27

28 grid[x][y] = lvl;

29 q.emplace(x, y);

30 }

31 }

32 }

33

34 using pqtype_t = tuple<int, int, int>;

35 priority_queue<pqtype_t> pq;

36

37 int res = grid[0][0];

38

39 pq.emplace(grid[0][0], 0, 0);

40 grid[0][0] = -grid[0][0];

41 while (!pq.empty()) {

42 const auto [v, a, b] = pq.top();

43 pq.pop();

44

45 res = min(res, -grid[a][b]);

46 if (a == n - 1 && b == n - 1) return res - 1;

47

48 for (int k = 0; k < 4; k++) {

49 const int x = a + offset[k + 1];

50 const int y = b + offset[k];

51

52 if (x < 0 || x >= n || y < 0 || y >= n) continue;

53 if (grid[x][y] < 0) continue;

54

55 pq.emplace(grid[x][y], x, y);

56 grid[x][y] = -grid[x][y];

57 }

58 }

59

60 return 0;

61 }

62 };