제출 #1365369

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365369		kahoul	Toy (CEOI24_toy)	C++20	0 / 100	0 ms	344 KiB

Main

#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 << xc << ' ' << yc << '\n';

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

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

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

            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 + (canMoveHorizontal ? dx : 0), y}});
                    break;
                }
            }
        }
        
        for (auto dy : ds) {
            if (!(yc + dy >= 0 && yc + dy < h)) continue;
            bool canMoveVertical = yv + dy >= 0 && yv + dy + l - 1 < h && placed[yv + dy][xc] != 'X' && placed[yv + l - 1 + dy][xc] != 'X';

            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 + (canMoveVertical ? dy : 0)}});
                    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";
    }
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 0 / 14
• 서브태스크 2: 0 / 21
• 서브태스크 3: 0 / 9
• 서브태스크 4: 0 / 29
• 서브태스크 5: 0 / 27