generated from threeal/project-starter
-
Notifications
You must be signed in to change notification settings - Fork 1
/
solution.cpp
82 lines (71 loc) · 2.17 KB
/
solution.cpp
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 <algorithm>
#include <limits>
#include <queue>
#include <tuple>
#include <vector>
class Solution {
public:
int maximumSafenessFactor(std::vector<std::vector<int>>& grid) {
const int h = grid.size();
const int w = grid.front().size();
std::queue<std::tuple<int, int>> thiefs{};
for (int y{h - 1}; y >= 0; --y) {
for (int x{w - 1}; x >= 0; --x) {
if (grid[y][x] == 1) {
grid[y][x] = 0;
thiefs.push({y, x});
} else {
grid[y][x] = std::numeric_limits<int>::max();
}
}
}
for (int step{1}; !thiefs.empty(); ++step) {
for (std::size_t i{thiefs.size()}; i > 0; --i) {
const auto [y, x] = thiefs.front();
if (y > 0 && step < grid[y - 1][x]) {
grid[y - 1][x] = step;
thiefs.push({y - 1, x});
}
if (x > 0 && step < grid[y][x - 1]) {
grid[y][x - 1] = step;
thiefs.push({y, x - 1});
}
if (y + 1 < h && step < grid[y + 1][x]) {
grid[y + 1][x] = step;
thiefs.push({y + 1, x});
}
if (x + 1 < w && step < grid[y][x + 1]) {
grid[y][x + 1] = step;
thiefs.push({y, x + 1});
}
thiefs.pop();
}
}
std::priority_queue<std::tuple<int, int, int>> steps{};
std::vector<std::vector<bool>> visited(h, std::vector(w, false));
steps.push({grid[0][0], 0, 0});
visited[0][0] = true;
while (!steps.empty()) {
const auto [score, y, x] = steps.top();
if (y == h - 1 && x == w - 1) return score;
steps.pop();
if (y > 0 && !visited[y - 1][x]) {
steps.push({std::min(score, grid[y - 1][x]), y - 1, x});
visited[y - 1][x] = true;
}
if (x > 0 && !visited[y][x - 1]) {
steps.push({std::min(score, grid[y][x - 1]), y, x - 1});
visited[y][x - 1] = true;
}
if (y + 1 < w && !visited[y + 1][x]) {
steps.push({std::min(score, grid[y + 1][x]), y + 1, x});
visited[y + 1][x] = true;
}
if (x + 1 < h && !visited[y][x + 1]) {
steps.push({std::min(score, grid[y][x + 1]), y, x + 1});
visited[y][x + 1] = true;
}
}
return 0;
}
};