Submission #1045724

#TimeUsernameProblemLanguageResultExecution timeMemory
1045724alex_2008Toy (CEOI24_toy)C++14
9 / 100
10 ms17244 KiB
#include <iostream> #include <cmath> #include <algorithm> #include <vector> #include <map> #include <queue> #include <stack> #include <set> typedef long long ll; using namespace std; const int N = 1510; char a[N][N]; bool used[N][N]; int tp[N][N]; int dwn[N][N]; int lft[N][N]; int rght[N][N]; int w, h, k, l; int cnt(int x1, int y1, int x2, int y2) { return a[x2][y2] - a[x1][y2] - a[x2][y1] + a[x1][y1]; } pair<int, int> vertical_range(int x, int y) { if (tp[x][y] + dwn[x][y] <= l) return { 1, 0 }; int r_min = x - tp[x][y] + 1; int r_mx = x + dwn[x][y] - l; return make_pair(r_min, r_mx); } pair<int, int> horizontal_range(int x, int y) { if (lft[x][y] + rght[x][y] <= k) return { 1, 0 }; int c_min = x - lft[x][y] + 1; int c_mx = x + rght[x][y] - k; return make_pair(c_min, c_mx); } bool intersect(pair<int, int> x, pair<int, int> y) { pair<int, int> c = make_pair(max(x.first, y.first), min(x.second, y.second)); if (c.first > c.second) return false; return true; } bool ch(int x, int y) { if ((tp[x][y] + dwn[x][y]) > l && (lft[x][y] + rght[x][y]) > k) return true; return false; } int main() { cin >> w >> h >> k >> l; int xh, yh, xv, yv; cin >> xh >> yh >> xv >> yv; xh++; xv++; yh++; yv++; swap(xh, yh); swap(xv, yv); //cout << xh << " " << yh << " " << xv << " " << yv << "\n"; int fx = -1, fy = -1; for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { cin >> a[i][j]; if (a[i][j] == '*') { fx = i; fy = j; } } } for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { if (a[i][j] == 'X') { lft[i][j] = 0; tp[i][j] = 0; } else { lft[i][j] = lft[i][j - 1] + 1; tp[i][j] = tp[i - 1][j] + 1; } lft[i][j] = min(lft[i][j], k); tp[i][j] = min(tp[i][j], l); } } for (int i = h; i >= 1; i--) { for (int j = w; j >= 1; j--) { if (a[i][j] == 'X') { rght[i][j] = 0; dwn[i][j] = 0; } else { rght[i][j] = rght[i][j + 1] + 1; dwn[i][j] = dwn[i + 1][j] + 1; } rght[i][j] = min(rght[i][j], k); dwn[i][j] = min(dwn[i][j], l); } } used[xh][yv] = true; queue <pair<int, int>> Q; Q.push({ xh, yv }); while (!Q.empty()) { int x = Q.front().first, y = Q.front().second; Q.pop(); //cout << "? " << x << " " << y << "\n"; if (x > 1) { if (intersect(horizontal_range(x, y), horizontal_range(x - 1, y)) && ch(x - 1, y)) { if (!used[x - 1][y]) { used[x - 1][y] = true; Q.push({ x - 1, y }); } } } if (x < h) { if (intersect(horizontal_range(x, y), horizontal_range(x + 1, y)) && ch(x + 1, y)) { if (!used[x + 1][y]) { used[x + 1][y] = true; Q.push({ x + 1, y }); } } } if (y > 1) { if (intersect(vertical_range(x, y), vertical_range(x, y - 1)) && ch(x, y - 1)) { if (!used[x][y - 1]) { used[x][y - 1] = true; Q.push({ x, y - 1 }); } } } if (y < w) { if (intersect(vertical_range(x, y), vertical_range(x, y + 1)) && ch(x, y + 1)) { if (!used[x][y + 1]) { used[x][y + 1] = true; Q.push({ x, y + 1 }); } } } } if (used[fx][fy]) cout << "YES\n"; else cout << "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...