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
| class Solution {
public:
int maximumMinutes(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), ds[] = {0, 1, 0, -1, 0};
queue<pair<int, int>> q;
vector<vector<int>> dis(m, vector<int>(n, -1));
for (int i = 0; i < m; ++i)
for (int j = 0; j < n; ++j)
if (grid[i][j] == 1)
dis[i][j] = 0, q.emplace(i, j);
while (q.size()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i], ny = y + ds[i + 1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || dis[nx][ny] != -1 || grid[nx][ny] == 2) continue;
dis[nx][ny] = dis[x][y] + 1;
q.emplace(nx, ny);
}
}
auto check = [&](int k) {
if (dis[0][0] != -1 && dis[0][0] <= k) return false;
queue<pair<int, int>> q;
q.emplace(0, 0);
vector<vector<int>> dep(m, vector<int>(n, -1));
dep[0][0] = 0;
while (q.size()) {
auto [x, y] = q.front(); q.pop();
for (int i = 0; i < 4; ++i) {
int nx = x + ds[i], ny = y + ds[i + 1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n || dep[nx][ny] != -1 || grid[x][y] == 2) continue;
if (dis[nx][ny] != -1 &&
dep[x][y] + 1 + k >= dis[nx][ny] + (nx == m - 1 && ny == n - 1)) continue;
dep[nx][ny] = dep[x][y] + 1;
q.emplace(nx, ny);
}
}
return dep[m - 1][n - 1] != -1;
};
int ans = -1, l = 0, r = 1e9;
while (l <= r) {
int mid = l + r >> 1;
if (check(mid)) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans;
}
};
|