제출 #1364988

#제출 시각아이디문제언어결과실행 시간메모리
1364988kahoulToy (CEOI24_toy)C++20
0 / 100
0 ms344 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 << yc << ' ' << xc << '\n';

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

        // dx = +1
        if (xh + k < w && placed[yc][xh + k] != 'X') {
            int max_above = max(0, yc - l + 1);
            int min_below = min(h - 1, yc + l - 1);

            for (int y = max(0, yc - l + 1); y <= min(h - 1, yc + l - 1); y++) {
                if (y == yc) continue;
                if (y < yc && placed[y][xv + 1] == 'X') max_above = max(max_above, y + 1);
                if (y > yc && placed[y][xv + 1] == 'X') min_below = min(min_below, y - 1);
            }

            for (int y = max_above; y <= min_below - l + 1; y++) {
                bool yeah = 1;
                for (int ny = y; ny < y + l; ny++) {
                    if (placed[ny][xc] == 'X') {
                        yeah = 0;
                    }
                }
                if (yeah) {
                    bfs.push_back({{xh + 1, yc}, {xv + 1, y}});
                }
            }
        }

        // dx = -1
        if (xh - 1 >= 0 && placed[yc][xh - 1] != 'X') {
            int max_above = max(0, yc - l + 1);
            int min_below = min(h - 1, yc + l - 1);

            for (int y = max(0, yc - l + 1); y <= min(h - 1, yc + l - 1); y++) {
                if (y == yc) continue;
                if (y < yc && placed[y][xv - 1] == 'X') max_above = max(max_above, y + 1);
                if (y > yc && placed[y][xv - 1] == 'X') min_below = min(min_below, y - 1);
            }

            for (int y = max_above; y <= min_below - l + 1; y++) {
                bool yeah = 1;
                for (int ny = y; ny < y + l; ny++) {
                    if (placed[ny][xc] == 'X') yeah = 0;
                }
                if (yeah) {
                    bfs.push_back({{xh - 1, yc}, {xv - 1, y}});
                }
            }
        }

        // dy = -1
        if (yh - 1 >= 0 && placed[yh - 1][xc] != 'X') {
            int max_left = max(0, xc - k + 1);
            int min_right = min(w - 1, xc + k - 1);

            for (int x = max(0, xc - k + 1); x <= min(w - 1, xc + k - 1); x++) {
                if (x == xc) continue;
                if (x < xc && placed[yc - 1][x] == 'X') max_left = max(max_left, x + 1);
                if (x > xc && placed[yc - 1][x] == 'X') min_right = max(min_right, x - 1);
            }

            for (int x = max_left; x <= min_right - k + 1; x++) {
                bool yeah = 1;
                for (int nx = x; nx < min_right - k; nx++) {
                    if (placed[yc - 1][x] == 'X') yeah = 0;
                }
                if (yeah) bfs.push_back({{x, yc - 1}, {xv, yv - 1}});
            }
        }

        // dy = +1
        if (yv + l < h && placed[yh + 1][xc] != 'X') {
            int max_left = max(0, xc - k + 1);
            int min_right = min(w - 1, xc + k - 1);

            for (int x = max(0, xc - k + 1); x <= min(w - 1, xc + k - 1); x++) {
                if (x == xc) continue;
                if (x < xc && placed[yc + 1][x] == 'X') max_left = max(max_left, x + 1);
                if (x > xc && placed[yc + 1][x] == 'X') min_right = max(min_right, x - 1);
            }

            for (int x = max_left; x <= min_right - k + 1; x++) {
                bool yeah = 1;
                for (int nx = x; nx < min_right - k; nx++) {
                    if (placed[yc + 1][x] == 'X') yeah = 0;
                }
                if (yeah) bfs.push_back({{x, yc + 1}, {xv, yv + 1}});
            }
        }
    }

    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";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…