제출 #1364944

#제출 시각아이디문제언어결과실행 시간메모리
1364944kahoulToy (CEOI24_toy)C++20
0 / 100
8 ms668 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>> pos_h_small(h, vector<bool>(w, 0));
    vector<vector<bool>> pos_h_all(h, vector<bool>(w, 0));
    vector<vector<bool>> blocked_h(h, vector<bool>(w, 0));

    for (int y = 0; y < h; y++) {
        int last_blocked = -10000;
        for (int x = 0; x < k - 1; x++) {
            if (placed[y][x] == 'X') last_blocked = x;
        }
        for (int x = k - 1; x < w; x++) {
            if (placed[y][x] == 'X') last_blocked = x;
            if (x - last_blocked < k) blocked_h[y][x - k + 1] = 1;
        }
    }

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

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

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

        int dy[] = {-1, +1, 0, 0};
        int dx[] = {0, 0, -1, +1};

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (nx + k - 1 >= w) continue;
            if (ny >= h) continue;
            if (nx < 0) continue;
            if (ny < 0) continue;

            if (blocked_h[ny][nx]) continue;

            bfs.push_back({nx, ny});
        }
    }

    for (int y = 0; y < h; y++) {
        int last_good = -10000;
        for (int x = 0; x < w; x++) {
            if (pos_h_small[y][x]) last_good = x;
            if (x - last_good < k) pos_h_all[y][x] = 1;
        }
    }

    vector<vector<bool>> pos_w_small(h, vector<bool>(w, 0));
    vector<vector<bool>> pos_w_all(h, vector<bool>(w, 0));
    vector<vector<bool>> blocked_w(h, vector<bool>(w, 0));

    for (int x = 0; x < w; x++) {
        int last_blocked = -10000;
        for (int y = 0; y < l - 1; y++) {
            if (placed[y][x] == 'X') last_blocked = y;
        }
        for (int y = l - 1; y < h; y++) {
            if (placed[y][x] == 'X') last_blocked = y;
            if (y - last_blocked < l) blocked_w[y - l + 1][x] = 1;
        }
    }

    bfs.clear();
    bfs.push_back({xv, yv});

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

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

        int dy[] = {-1, +1, 0, 0};
        int dx[] = {0, 0, -1, +1};

        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];

            if (nx >= w) continue;
            if (ny + l - 1 >= h) continue;
            if (nx < 0) continue;
            if (ny < 0) continue;

            if (blocked_w[ny][nx]) continue;

            bfs.push_back({nx, ny});
        }
    }

    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            pos_w_all[y][x] = pos_w_small[max(y - l + 1, 0)][x];
        }
    }


    for (int x = 0; x < w; x++) {
        int last_good = -10000;
        for (int y = 0; y < h; y++) {
            if (pos_w_small[y][x]) last_good = y;
            if (y - last_good < l) pos_w_all[y][x] = 1;
        }
    }

    /* cout << "Vertical (small - all - blocked)\n";

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

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

    for (int y = 0; y < h; y++) {
        for (int x = 0; x < w; x++) {
            cout << (bool)(blocked_w[y][x]);
        }
        cout << '\n';
    }
    cout << '\n';
    cout << "Horizontal (small - all)\n";

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

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

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

    if (pos_w_all[desty][destx] && pos_h_all[desty][destx]) {
         cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…