-
Notifications
You must be signed in to change notification settings - Fork 0
/
1970. Last Day Where You Can Still Cross.cpp
67 lines (53 loc) · 1.32 KB
/
1970. Last Day Where You Can Still Cross.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
LeetCode
1970. Last Day Where You Can Still Cross
class Solution {
public:
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
int ans = 0;
int l = 1;
int r = cells.size() - 1;
while (l <= r) {
const int m = (l + r) / 2;
if (canWalk(m, row, col, cells)) {
ans = m;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
private:
const vector<int> dirs{0, 1, 0, -1, 0};
bool canWalk(int day, int row, int col, const vector<vector<int>>& cells) {
vector<vector<int>> matrix(row, vector<int>(col));
for (int i = 0; i < day; ++i) {
const int x = cells[i][0] - 1;
const int y = cells[i][1] - 1;
matrix[x][y] = 1;
}
queue<pair<int, int>> q;
for (int j = 0; j < col; ++j)
if (matrix[0][j] == 0) {
q.emplace(0, j);
matrix[0][j] = 1;
}
while (!q.empty()) {
const auto [i, j] = q.front();
q.pop();
for (int k = 0; k < 4; ++k) {
const int x = i + dirs[k];
const int y = j + dirs[k + 1];
if (x < 0 || x == row || y < 0 || y == col)
continue;
if (matrix[x][y] == 1)
continue;
if (x == row - 1)
return true;
q.emplace(x, y);
matrix[x][y] = 1;
}
}
return false;
}
};