lc
lc1970
二分猜答案+BFS
找能从网格第一行走到最后一行的最晚日期
核心是二分判断某天前的格子封堵后是否还能通行
vis 防重复走 a存储每次场景
class Solution {
vector<array<int, 2>> dirs{{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
public:
int latestDayToCross(int row, int col, vector<vector<int>>& cells) {
auto check = [&](int v) -> bool {
vector<vector<int>> a(row, vector<int>(col));
vector<vector<int>> vis(row, vector<int>(col));
for (int i = 0; i < v; i++) {
int x = cells[i][0] - 1, y = cells[i][1] - 1;
a[x][y] = 1;
}
queue<array<int, 2>> q;
for (int j = 0; j < col; j++) {
if (a[0][j] == 0) {
vis[0][j] = v + 1;
q.push({0, j});
}
}
while (!q.empty()) {
auto [x, y] = q.front();
q.pop();
if (x == row - 1) return true;
for (auto [dx, dy]: dirs) {
int nx = x + dx, ny = y + dy;
if (0 <= nx && nx < row && 0 <= ny && ny < col && vis[nx][ny] != v + 1 && a[nx][ny] == 0) {
q.push({nx, ny});
vis[nx][ny] = v + 1;
}
}
}
return false;
};
int left = 0, right = cells.size();
int ans = 0;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(mid)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return ans;
}
};
不够优雅 但绝对正确的闭区间二分ovo
