| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1256876 | christhegamechanger | 축제 (IOI25_festival) | C++17 | 0 ms | 0 KiB |
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
int N, M;
vector<int> T, H;
void initialize(vector<int> t, vector<int> h) {
N = t.size();
M = h.size();
T = t;
H = h;
}
bool can_reach(int L, int R, int S, int D) {
// If start and destination are the same
if (S == D) return true;
// BFS to find path from (0,S) to (0,D) within columns [L,R]
vector<vector<bool>> visited(N, vector<bool>(R - L + 1, false));
queue<pair<int, int>> q;
// Start from (0,S)
q.push({0, S - L});
visited[0][S - L] = true;
// Direction vectors for 4-connected grid
int dr[] = {-1, 1, 0, 0};
int dc[] = {0, 0, -1, 1};
while (!q.empty()) {
auto [row, col_idx] = q.front();
q.pop();
int actual_col = col_idx + L;
// Check if we reached the destination
if (row == 0 && actual_col == D) {
return true;
}
// Try all 4 directions
for (int i = 0; i < 4; i++) {
int new_row = row + dr[i];
int new_col_idx = col_idx + dc[i];
int new_actual_col = new_col_idx + L;
// Check bounds
if (new_row < 0 || new_row >= N) continue;
if (new_col_idx < 0 || new_col_idx >= R - L + 1) continue;
// Check if already visited
if (visited[new_row][new_col_idx]) continue;
// Check if cell is free of vegetation (T[row] > H[col])
if (T[new_row] <= H[new_actual_col]) continue;
// Mark as visited and add to queue
visited[new_row][new_col_idx] = true;
q.push({new_row, new_col_idx});
}
}
return false;
}