MyLeetcode/cpp_solutions/2812.cpp at main · Kaminyou/MyLeetcode · GitHub

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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
class Solution {
public:
    vector<pair<int ,int >> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        queue<pair<int, int>> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) q.push({i, j});
            }
        }

        while (!q.empty()) {
            auto [i, j] = q.front();
            q.pop();
            for (auto& direction : directions) {
                int x = i + direction.first;
                int y = j + direction.second;
                if (x < 0 || x >= n || y < 0 || y >= n) continue;
                if (grid[x][y] != 0) continue;
                grid[x][y] = grid[i][j] + 1;
                q.push({x, y});
            }
        }

        priority_queue<tuple<int, int, int>> pq;
        pq.push({grid[0][0], 0, 0});
        while (get<1>(pq.top()) < n - 1 || get<2>(pq.top()) < n - 1) {
            auto [val, i, j] = pq.top();
            pq.pop();
            for (auto& direction : directions) {
                int x = i + direction.first;
                int y = j + direction.second;
                if (x < 0 || x >= n || y < 0 || y >= n) continue;
                if (grid[x][y] < 0) continue;
                pq.push({min(val, grid[x][y]), x, y});
                grid[x][y] *= -1;
            }
        }
        return get<0>(pq.top()) - 1;
    }
};

class DisjointSet {
private:
    vector<int> parents;
    vector<int> ranks;
public:
    DisjointSet(int n) {
        parents.resize(n, 0);
        ranks.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parents[i] = i;
        }
    }
    int find(int x) {
        if (parents[x] == x) return parents[x];
        return parents[x] = find(parents[x]);
    }
    void join(int x, int y) {
        int pX = find(x);
        int pY = find(y);
        if (pX == pY) return;
        if (ranks[pX] > ranks[pY]) parents[pY] = pX;
        else if (ranks[pX] < ranks[pY]) parents[pX] = pY;
        else {
            parents[pY] = pX;
            ranks[pX]++;
        }
    }
};
class Solution {
public:
    vector<pair<int, int>> directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    int maximumSafenessFactor(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> distances(n, vector<int>(n, INT_MAX));
        queue<pair<int, int>> q;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    q.push({i, j});
                    distances[i][j] = 0;
                }
            }
        }
        while (!q.empty()) {
            int m = q.size();
            while (m--) {
                auto [x, y] = q.front();
                int curr = distances[x][y];
                q.pop();
                for (auto& direction : directions) {
                    int xx = x + direction.first;
                    int yy = y + direction.second;
                    if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
                    if (distances[xx][yy] != INT_MAX) continue;
                    distances[xx][yy] = curr + 1;
                    q.push({xx, yy});
                }
            }
        }
        vector<pair<int, pair<int, int>>> v;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                v.push_back({-distances[i][j], {i, j}});
            }
        }
        sort(v.begin(), v.end());
        DisjointSet* disjointSet = new DisjointSet(n * n);
        for (auto& vv : v) {
            auto [d, p] = vv;
            auto [x, y] = p;
            for (auto& direction : directions) {
                int xx = x + direction.first;
                int yy = y + direction.second;
                if (xx < 0 || xx >= n || yy < 0 || yy >= n) continue;
                if (distances[xx][yy] < -d) continue;
                disjointSet->join(x * n + y, xx * n + yy);
            }
            if (disjointSet->find(0) == disjointSet->find(n * n - 1)) return -d;
        }
        return -1;
    }
};