Submission #1182074

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182074		Cyanmond	Toy (CEOI24_toy)	C++20	100 / 100	54 ms	3736 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

array<pair<int, int>, 4> dxy = {{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}};

void solve() {
    int W, H, K, L;
    cin >> W >> H >> K >> L;
    pair<int, int> s_pos, g_pos;
    {
        int ax, ay, bx, by;
        cin >> ax >> ay >> bx >> by;
        s_pos = make_pair(ay, bx);
    }
    vector<string> s(H);
    for (auto &e : s) {
        cin >> e;
    }
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (s[i][j] == '*') {
                g_pos = make_pair(i, j);
            }
        }
    }

    vector<vector<bool>> s_ver(H - L + 1, vector<bool>(W));
    vector<vector<bool>> s_hor(H, vector<bool>(W - K + 1));
    for (int j = 0; j < W; ++j) {
        int last_pos = -1;
        for (int i = 0; i < H; ++i) {
            if (s[i][j] == 'X') {
                last_pos = i;
            }
            if (i >= L - 1) {
                s_ver[i - L + 1][j] = last_pos < i - L + 1;
            }
        }
    }
    for (int i = 0; i < H; ++i) {
        int last_pos = -1;
        for (int j = 0; j < W; ++j) {
            if (s[i][j] == 'X') {
                last_pos = j;
            }
            if (j >= K - 1) {
                s_hor[i][j - K + 1] = last_pos < j - K + 1;
            }
        }
    }

    auto bridge = [&](pair<int, int> f, int dir) {
        auto &[fx, fy] = f;
        auto &[ax, ay] = dxy[dir];
        int nx = fx + ax, ny = fy + ay;

        if (dir % 2 == 0) {
            // vertical
            bool ret = false;
            for (int i = max(0, fy - K + 1); i <= min(W - K, fy); ++i) {
                bool valid = s_hor[fx][i] and s_hor[nx][i];
                if (valid) {
                    ret = true;
                    break;
                }
            }
            return ret;
        } else {
            // horizontal
            bool ret = false;
            for (int i = max(0, fx - L + 1); i <= min(H - L, fx); ++i) {
                bool valid = s_ver[i][fy] and s_ver[i][ny];
                if (valid) {
                    ret = true;
                    break;
                }
            }
            return ret;
        }
    };

    queue<pair<int, int>> que;
    que.push(s_pos);
    vector<vector<bool>> reachable(H, vector<bool>(W));
    reachable[s_pos.first][s_pos.second] = true;
    while (not que.empty()) {
        auto f = que.front();
        que.pop();
        for (int i = 0; i < 4; ++i) {
            auto &[fx, fy] = f;
            auto &[ax, ay] = dxy[i];
            int nx = fx + ax, ny = fy + ay;
            if (nx < 0 or nx >= H or ny < 0 or ny >= W) {
                continue;
            }
            if (reachable[nx][ny]) {
                continue;
            }
            if (bridge(f, i)) {
                // cerr << nx << ' ' << ny << endl;
                reachable[nx][ny] = true;
                que.push(make_pair(nx, ny));
            }
        }
    }

    string ans = reachable[g_pos.first][g_pos.second] ? "YES" : "NO";
    cout << ans << endl;
}

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

    solve();
    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27