1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

class Solution {
public:
    int maximumSafenessFactor(std::vector<std::vector<int>>& grid) {
        if (grid[0][0] || grid.back().back()) {
            return 0;
        }
        
        int n = grid.size();
        std::vector<std::vector<int>> factor(n, std::vector<int>(n, 0x7fff'ffff));
        std::queue<std::pair<int, std::pair<int, int>>> q;
        
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j]) {
                    q.push({0, {i, j}});
                    factor[i][j] = 0;
                }
            }
        }
        
        int dirs[4][2] = { {1, 0}, {0, 1}, {-1, 0}, {0, -1} };
        while (!q.empty()) {
            int f = q.front().first;
            int x = q.front().second.first;
            int y = q.front().second.second;
            q.pop();
            if (f > factor[x][y]) {
                continue;
            }
            
            ++f;
            for (auto& dir : dirs) {
                int xx = x + dir[0];
                int yy = y + dir[1];
                if (xx < 0 || xx >= n || yy < 0 || yy >= n) {
                    continue;
                }
                if (f < factor[xx][yy]) {
                    factor[xx][yy] = f;
                    q.push({f, {xx, yy}});
                }
            }
        }
        
        std::priority_queue<std::pair<int, std::pair<int, int>>> pq;
        std::vector<std::vector<int>> visited(n, std::vector<int>(n, 0));
        pq.push({factor[0][0], {0, 0}});
        visited[0][0] = factor[0][0];
        
        while (!pq.empty()) {
            int f = pq.top().first;
            int x = pq.top().second.first;
            int y = pq.top().second.second;
            if (x == n - 1 && y == n - 1) {
                return f;
            }
            pq.pop();
            if (f < visited[x][y]) {
                continue;
            }
            for (auto& dir : dirs) {
                int xx = x + dir[0];
                int yy = y + dir[1];
                if (xx < 0 || xx >= n || yy < 0 || yy >= n) {
                    continue;
                }
                int nf = std::min(f, factor[xx][yy]);
                if (nf > visited[xx][yy]) {
                    visited[xx][yy] = nf;
                    pq.push({nf, {xx, yy}});
                }
            }
        }
        
        return 0;
    }
};