Submission #1182040

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182040		Cyanmond	Toy (CEOI24_toy)	C++20	0 / 100	0 ms	328 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(bx, ay);
    }
    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);
            }
        }
    }

    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(H - K, fy); ++i) {
                bool valid = true;
                for (int j = i; j < i + K; ++j) {
                    if (s[j][fy] == '*' or s[j][ny] == '*') {
                        valid = false;
                        break;
                    }
                }
                if (valid) {
                    ret = true;
                    break;
                }
            }
            return ret;
        } else {
            // horizontal
            bool ret = false;
            for (int i = max(0, fx - L + 1); i <= min(W - L, fx); ++i) {
                bool valid = true;
                for (int j = i; j < i + L; ++j) {
                    if (s[fx][j] == '*' or s[nx][j] == '*') {
                        valid = false;
                        break;
                    }
                }
                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)) {
                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: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 9
• Subtask 4: 0 / 29
• Subtask 5: 0 / 27