제출 #1212412

#제출 시각아이디문제언어결과실행 시간메모리
1212412yanbToy (CEOI24_toy)C++20
73 / 100
1597 ms75848 KiB
#include <bits/stdc++.h> #define int long long using namespace std; void dfs(int v, vector<vector<int>> &g, vector<bool> &uu) { if (uu[v]) return; uu[v] = 1; for (int u : g[v]) dfs(u, g, uu); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int w, h, k, l; cin >> w >> h >> k >> l; int xh, yh, xv, yv; cin >> xh >> yh >> xv >> yv; vector<string> a(h + 2); for (int j = 0; j < w + 2; j++) { a[0] += 'X'; a[h + 1] += 'X'; } for (int i = 1; i <= h; i++) { string t; cin >> t; a[i] = 'X' + t + 'X'; } w += 2, h += 2; int sx = xv + 1, sy = yh + 1; int ex, ey; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (a[i][j] == '*') { ex = j, ey = i; } } } vector<vector<int>> Bl(h, vector<int>(w)), Br(h, vector<int>(w)), Bu(h, vector<int>(w)), Bd(h, vector<int>(w)); for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { for (int x = j; x >= 0; x--) { if (a[i][x] == 'X') { Bl[i][j] = x; break; } } for (int x = j; x < w; x++) { if (a[i][x] == 'X') { Br[i][j] = x; break; } } for (int y = i; y >= 0; y--) { if (a[y][j] == 'X') { Bu[i][j] = y; break; } } for (int y = i; y < h; y++) { if (a[y][j] == 'X') { Bd[i][j] = y; break; } } } } vector<vector<int>> g(w * h); // y * w + x for (int y = 0; y < h; y++) { for (int x = 0; x < w - 1; x++) { if (a[y][x] != 'X' && a[y][x + 1] != 'X') { int U = max(Bu[y][x], Bu[y][x + 1]); int D = min(Bd[y][x], Bd[y][x + 1]); if (D - U - 1 >= l) { g[y * w + x].push_back(y * w + (x + 1)); g[y * w + (x + 1)].push_back(y * w + x); } } } } for (int y = 0; y < h - 1; y++) { for (int x = 0; x < w; x++) { if (a[y][x] != 'X' && a[y + 1][x] != 'X') { int L = max(Bl[y][x], Bl[y + 1][x]); int R = min(Br[y][x], Br[y + 1][x]); if (R - L - 1 >= k) { g[y * w + x].push_back((y + 1) * w + x); g[(y + 1) * w + x].push_back(y * w + x); } } } } vector<bool> uu(w * h); dfs(sy * w + sx, g, uu); cout << (uu[ey * w + ex] ? "YES\n" : "NO\n"); }
#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...