Submission #1214792

#TimeUsernameProblemLanguageResultExecution timeMemory
1214792spetrToy (CEOI24_toy)C++20
9 / 100
10 ms14408 KiB
#include <bits/stdc++.h> using namespace std; const int MAX = 1505; int w, h, k, l; int kx, ky, lx, ly; char graf[MAX][MAX]; bool visited[MAX][MAX]; int leva[MAX][MAX], prava[MAX][MAX], up[MAX][MAX], down[MAX][MAX]; int intersect(int l1, int r1, int l2, int r2) { return max(0, min(r1, r2) - max(l1, l2) + 1); } void dfs(int y, int x) { visited[y][x] = true; if (graf[y][x] == '*') { cout << "YES\n"; exit(0); } static const int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; for (int i = 0; i < 4; i++) { int nx = x + dirs[i][0]; int ny = y + dirs[i][1]; if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue; if (graf[ny][nx] == 'X' || visited[ny][nx]) continue; int oldL = x - prava[y][x], oldR = x + leva[y][x]; int newL = nx - prava[ny][nx], newR = nx + leva[ny][nx]; if (intersect(oldL, oldR, newL, newR) < k) continue; int oldU = y - down[y][x], oldD = y + up[y][x]; int newU = ny - down[ny][nx], newD = ny + up[ny][nx]; if (intersect(oldU, oldD, newU, newD) < l) continue; dfs(ny, nx); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> w >> h >> k >> l; cin >> kx >> ky >> lx >> ly; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { cin >> graf[i][j]; } } // předpočítej doleva/doprava for (int i = 0; i < h; i++) { int cntL = 0, cntR = 0; for (int j = 0; j < w; j++) { if (graf[i][j] != 'X') { prava[i][j] = cntR++; } else cntR = 0; } for (int j = w-1; j >= 0; j--) { if (graf[i][j] != 'X') { leva[i][j] = cntL++; } else cntL = 0; } } // předpočítej nahoru/dolů for (int j = 0; j < w; j++) { int cntU = 0, cntD = 0; for (int i = 0; i < h; i++) { if (graf[i][j] != 'X') { down[i][j] = cntD++; } else cntD = 0; } for (int i = h-1; i >= 0; i--) { if (graf[i][j] != 'X') { up[i][j] = cntU++; } else cntU = 0; } } dfs(ky, kx); cout << "NO\n"; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...