제출 #1365502

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1365502		kahoul	Toy (CEOI24_toy)	C++20	100 / 100	396 ms	197068 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<int>> left (h, vector<int>(w, 0));
    vector<vector<int>> right(h, vector<int>(w, 0));
    vector<vector<int>> up   (h, vector<int>(w, 0));
    vector<vector<int>> down (h, vector<int>(w, 0));

    for (int y = 0; y < h; y++) {
        int leftmost = 0;
        for (int x = 0; x < w; x++) {
            if (placed[y][x] == 'X') leftmost = x + 1;
            left[y][x] = leftmost;
        }
        int rightleast = w - 1;
        for (int x = w - 1; x >= 0; x--) {
            if (placed[y][x] == 'X') rightleast = x - 1;
            right[y][x] = rightleast;
        }
    }

    for (int x = 0; x < w; x++) {
        int topleast = 0;
        for (int y = 0; y < h; y++) {
            if (placed[y][x] == 'X') topleast = y + 1;
            up[y][x] = topleast;
        }
        int bottomleast = h - 1;
        for (int y = h - 1; y >= 0; y--) {
            if (placed[y][x] == 'X') bottomleast = y - 1;
            down[y][x] = bottomleast;
        }
    }

    vector<vector<vector<pair<int, int>>>> rel(h, vector<vector<pair<int, int>>>(w));

    int ds[] = {-1, +1};
    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            for (auto dy : ds) {
                if (y + dy < 0 || y + dy >= h) continue;
                int l = max(left[y][x], left[y + dy][x]);
                int r = min(right[y][x], right[y + dy][x]);

                if (r - l + 1 >= k) rel[y][x].push_back({y + dy, x});
            }

            for (auto dx : ds) {
                if (x + dx < 0 || x + dx >= w) continue;
                int u = max(up[y][x], up[y][x + dx]);
                int d = min(down[y][x], down[y][x + dx]);

                if (d - u + 1 >= l) rel[y][x].push_back({y, x + dx});
            }
        }
    }

    vector<vector<bool>> visited(h, vector<bool>(w, 0));
    deque<pair<int, int>> bfs;
    bfs.push_back({max(yh, yv), max(xh, xv)});

    while (!bfs.empty()) {
        auto [y, x] = bfs.front();
        bfs.pop_front();

        if (visited[y][x]) continue;
        visited[y][x] = 1;

        for (auto [ny, nx] : rel[y][x]) {
            bfs.push_back({ny, nx});
        }
    }

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

    cout << (visited[desty][destx] ? "YES" : "NO") << '\n';
}

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