제출 #1342776

#제출 시각아이디문제언어결과실행 시간메모리
1342776vjudge1Toy (CEOI24_toy)C++20
100 / 100
101 ms42500 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int W, H, K, L;
    cin >> W >> H >> K >> L;

    int xh0, yh0, xv0, yv0;
    cin >> xh0 >> yh0 >> xv0 >> yv0;

    vector<string> g(H);
    int tx = -1, ty = -1;
    for (int y = 0; y < H; ++y) {
        cin >> g[y];
        for (int x = 0; x < W; ++x) {
            if (g[y][x] == '*') {
                tx = x;
                ty = y;
            }
        }
    }

    auto id = [W](int y, int x) {
        return y * W + x;
    };

    int N = H * W;
    vector<int> left(N), right(N), up(N), down(N);
    vector<char> good(N, 0), vis(N, 0);

    // left / right
    for (int y = 0; y < H; ++y) {
        int run = 0;
        for (int x = 0; x < W; ++x) {
            if (g[y][x] == 'X') run = 0;
            else ++run;
            left[id(y, x)] = run;
        }

        run = 0;
        for (int x = W - 1; x >= 0; --x) {
            if (g[y][x] == 'X') run = 0;
            else ++run;
            right[id(y, x)] = run;
        }
    }

    // up / down
    for (int x = 0; x < W; ++x) {
        int run = 0;
        for (int y = 0; y < H; ++y) {
            if (g[y][x] == 'X') run = 0;
            else ++run;
            up[id(y, x)] = run;
        }

        run = 0;
        for (int y = H - 1; y >= 0; --y) {
            if (g[y][x] == 'X') run = 0;
            else ++run;
            down[id(y, x)] = run;
        }
    }

    // good cell = possible intersection
    for (int y = 0; y < H; ++y) {
        for (int x = 0; x < W; ++x) {
            int p = id(y, x);
            if (g[y][x] == 'X') continue;

            bool okH = (left[p] + right[p] - 1 >= K);
            bool okV = (up[p] + down[p] - 1 >= L);
            if (okH && okV) good[p] = 1;
        }
    }

    int sx = xv0;   // initial intersection x
    int sy = yh0;   // initial intersection y
    int S = id(sy, sx);
    int T = id(ty, tx);

    if (!good[S] || !good[T]) {
        cout << "NO\n";
        return 0;
    }

    queue<int> q;
    q.push(S);
    vis[S] = 1;

    while (!q.empty()) {
        int p = q.front();
        q.pop();

        if (p == T) {
            cout << "YES\n";
            return 0;
        }

        int y = p / W;
        int x = p % W;

        // Move intersection left/right:
        // need common vertical space of length L in both columns
        if (x + 1 < W) {
            int np = p + 1;
            if (!vis[np] && good[np]) {
                int common = min(up[p], up[np]) + min(down[p], down[np]) - 1;
                if (common >= L) {
                    vis[np] = 1;
                    q.push(np);
                }
            }
        }
        if (x - 1 >= 0) {
            int np = p - 1;
            if (!vis[np] && good[np]) {
                int common = min(up[p], up[np]) + min(down[p], down[np]) - 1;
                if (common >= L) {
                    vis[np] = 1;
                    q.push(np);
                }
            }
        }

        // Move intersection up/down:
        // need common horizontal space of length K in both rows
        if (y + 1 < H) {
            int np = p + W;
            if (!vis[np] && good[np]) {
                int common = min(left[p], left[np]) + min(right[p], right[np]) - 1;
                if (common >= K) {
                    vis[np] = 1;
                    q.push(np);
                }
            }
        }
        if (y - 1 >= 0) {
            int np = p - W;
            if (!vis[np] && good[np]) {
                int common = min(left[p], left[np]) + min(right[p], right[np]) - 1;
                if (common >= K) {
                    vis[np] = 1;
                    q.push(np);
                }
            }
        }
    }

    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...