2812.cpp (1752B)
1 class Solution { 2 public: 3 int maximumSafenessFactor(vector<vector<int>> &grid) { 4 static int offset[] = {-1, 0, 1, 0, -1}; 5 const int n = size(grid); 6 7 using qtype_t = tuple<int, int>; 8 queue<qtype_t> q; 9 10 for (int i = 0; i < n; i++) { 11 for (int j = 0; j < n; j++) { 12 if (grid[i][j] != 1) continue; 13 q.emplace(i, j); 14 } 15 } 16 17 for (int lvl = 2; !q.empty(); lvl++) { 18 for (int k = q.size(); k > 0; k--) { 19 const auto [a, b] = q.front(); 20 q.pop(); 21 22 for (int k = 0; k < 4; k++) { 23 const int x = a + offset[k + 1]; 24 const int y = b + offset[k]; 25 26 if (x < 0 || x >= n || y < 0 || y >= n) continue; 27 if (grid[x][y]) continue; 28 29 grid[x][y] = lvl; 30 q.emplace(x, y); 31 } 32 } 33 } 34 35 using pqtype_t = tuple<int, int, int>; 36 priority_queue<pqtype_t> pq; 37 38 int res = grid[0][0]; 39 40 pq.emplace(grid[0][0], 0, 0); 41 grid[0][0] = -grid[0][0]; 42 while (!pq.empty()) { 43 const auto [v, a, b] = pq.top(); 44 pq.pop(); 45 46 res = min(res, -grid[a][b]); 47 if (a == n - 1 && b == n - 1) return res - 1; 48 49 for (int k = 0; k < 4; k++) { 50 const int x = a + offset[k + 1]; 51 const int y = b + offset[k]; 52 53 if (x < 0 || x >= n || y < 0 || y >= n) continue; 54 if (grid[x][y] < 0) continue; 55 56 pq.emplace(grid[x][y], x, y); 57 grid[x][y] = -grid[x][y]; 58 } 59 } 60 61 return 0; 62 } 63 };