BOJ 25919 - Lost Edge
단순한 BFS를 여러번 돌리는 문제지만, 쉽게 생각하지 않고 뭔가 시간초과가 날거같아서 좀 걸렸다.
const int dy[] = {-1, 0, 1, 0}, dx[] = {0, 1, 0, -1}, op[] = {2, 3, 0, 1};
void solve() {
int Y, X, L, E, K, sy, sx, ey, ex;
cin >> Y >> X >> L >> E >> K;
vvi b(Y, vi(X));
fv2(b);
for (int y = 0; y < Y; y++)
for (int x = 0; x < X; x++) {
if (b[y][x] == -3)
sy = y, sx = x;
if (b[y][x] == -2)
ey = y, ex = x;
}
debug(sy, sx);
auto kill = [&](int e) {
E += e;
while (E >= L) {
E -= L;
L++;
}
};
while (1) {
//print(b);
queue<pi> q;
q.push({sy, sx});
vector<bitset<100>> vis(100);
vis[sy][sx] = 1;
int any_improved = 0;
debug(L, E);
while (sz(q)) {
auto [y, x] = q.front();
q.pop();
for (int d = 0; d < 4; d++) {
int ny = y + dy[d], nx = x + dx[d];
if (ny >= 0 && ny < Y && nx >= 0 && nx < X) {
if (vis[ny][nx]) continue;
if (b[ny][nx] == -1) continue;
else if (b[ny][nx] == -2) {
if (L >= K) {
cout << 'O';
return;
}
} else if (L > b[ny][nx]) {
if (b[ny][nx] > 0) {
any_improved = 1;
kill(b[ny][nx]);
b[ny][nx] = 0;
vis[ny][nx] = 1;
q.push({ny, nx});
} else {
vis[ny][nx] = 1;
q.push({ny, nx});
}
}
}
}
}
out:;
if (!any_improved)break;
}
cout << 'X';
}
Comments