leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

2812.cpp (1752B)

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 };