Submission #1365021

#TimeUsernameProblemLanguageResultExecution timeMemory
1365021kahoulToy (CEOI24_toy)C++20
0 / 100
9 ms556 KiB
#include <bits/stdc++.h>
using namespace std;

int main () {
    int w, h, k, l;
    cin >> w >> h >> k >> l;

    int xh, yh, xv, yv;
    cin >> xh >> yh >> xv >> yv;

    int destx = -1, desty = -1;

    char placed[h][w];

    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            cin >> placed[y][x];
            if (placed[y][x] == '*') {
                desty = y;
                destx = x;
            }
        }
    }

    vector<vector<bool>> visited(h, vector<bool>(w, 0));

    typedef pair<int, int> pii;
    deque<pair<pii, pii>> bfs;
    bfs.push_back({{xh, yh}, {xv, yv}});

    while (!bfs.empty()) {
        auto [p1, p2] = bfs.front();
        auto [xh, yh] = p1;
        auto [xv, yv] = p2;
        bfs.pop_front();

        int yc = max(yh, yv);
        int xc = max(xh, xv);

        //cerr << "(" << xh << " " << yh << ") (" << xv << " " << yv << ") " << xc - xh + xc - xv + yc - yh + yc - yv << '\n';

        if (visited[yc][xc]) continue;
        visited[yc][xc] = 1;

        int ds[] = {-1, +1};

        for (auto dx : ds) {
            if (!(xh + dx >= 0 && xh + dx + k - 1 < w)) continue;
            if (placed[yc][xh + dx] == 'X' || placed[yc][xh + k - 1 + dx] == 'X') continue;

            int up_limit = max(0, yc - l + 1);
            int down_limit = min(h, yc + l - 1);

            int ymin = up_limit;
            int ymax = down_limit;

            for (int ny = up_limit; ny < yc; ny++) if (placed[ny][xc + dx] == 'X') ymin = ny;
            for (int ny = down_limit; ny > yc; ny--) if (placed[ny][xc + dx] == 'X') ymax = ny;

            for (int y = ymin; y <= ymax - l + 1; y++) {
                bool pass = 1;
                for (int ny = y; ny <= y + l; ny++) {
                    if (placed[ny][xc] == 'X') pass = 0;
                }
                if (pass) {
                    bfs.push_back({{xh + dx, yc}, {xc + dx, y}});
                    break;
                }
            }
        }
        
        for (auto dy : ds) {
            if (!(yv + dy >= 0 && yv + dy + l - 1 < h)) continue;
            if (placed[yv + dy][xc] == 'X' || placed[yv + l - 1 + dy][xc] == 'X') continue;

            int left_limit = max(0, xc - k + 1);
            int right_limit = min(h, xc + k - 1);

            int xmin = left_limit;
            int xmax = right_limit;

            for (int nx = left_limit; nx < xc; nx++) if (placed[yc + dy][nx] == 'X') xmin = nx;
            for (int nx = right_limit; nx > xc; nx--) if (placed[yc + dy][nx] == 'X') xmax = nx;

            for (int x = xmin; x <= xmax - k + 1; x++) {
                bool pass = 1;
                for (int nx = x; nx <= x + k; nx++) {
                    if (placed[yc][nx] == 'X') pass = 0;
                }
                if (pass) {
                    bfs.push_back({{x, yc + dy}, {xc, yv + dy}});
                    break;
                }
            }
        }
    }

    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            //cout << visited[y][x];
        }
        //cout << '\n';
    }

    if (visited[desty][destx]) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...