Submission #1214792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214792		spetr	Toy (CEOI24_toy)	C++20	9 / 100	10 ms	14408 KiB

Main

#include <bits/stdc++.h>
using namespace std;

const int MAX = 1505;
int w, h, k, l;
int kx, ky, lx, ly;
char graf[MAX][MAX];
bool visited[MAX][MAX];
int leva[MAX][MAX], prava[MAX][MAX], up[MAX][MAX], down[MAX][MAX];

int intersect(int l1, int r1, int l2, int r2) {
    return max(0, min(r1, r2) - max(l1, l2) + 1);
}

void dfs(int y, int x) {
    visited[y][x] = true;
    if (graf[y][x] == '*') {
        cout << "YES\n";
        exit(0);
    }
    static const int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int i = 0; i < 4; i++) {
        int nx = x + dirs[i][0];
        int ny = y + dirs[i][1];
        if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
        if (graf[ny][nx] == 'X' || visited[ny][nx]) continue;

        int oldL = x - prava[y][x], oldR = x + leva[y][x];
        int newL = nx - prava[ny][nx], newR = nx + leva[ny][nx];
        if (intersect(oldL, oldR, newL, newR) < k) continue;

        int oldU = y - down[y][x], oldD = y + up[y][x];
        int newU = ny - down[ny][nx], newD = ny + up[ny][nx];
        if (intersect(oldU, oldD, newU, newD) < l) continue;

        dfs(ny, nx);
    }
}

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

    cin >> w >> h >> k >> l;
    cin >> kx >> ky >> lx >> ly;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> graf[i][j];
        }
    }

    // předpočítej doleva/doprava
    for (int i = 0; i < h; i++) {
        int cntL = 0, cntR = 0;
        for (int j = 0; j < w; j++) {
            if (graf[i][j] != 'X') {
                prava[i][j] = cntR++;
            } else cntR = 0;
        }
        for (int j = w-1; j >= 0; j--) {
            if (graf[i][j] != 'X') {
                leva[i][j] = cntL++;
            } else cntL = 0;
        }
    }

    // předpočítej nahoru/dolů
    for (int j = 0; j < w; j++) {
        int cntU = 0, cntD = 0;
        for (int i = 0; i < h; i++) {
            if (graf[i][j] != 'X') {
                down[i][j] = cntD++;
            } else cntD = 0;
        }
        for (int i = h-1; i >= 0; i--) {
            if (graf[i][j] != 'X') {
                up[i][j] = cntU++;
            } else cntU = 0;
        }
    }

    dfs(ky, kx);
    cout << "NO\n";
    return 0;
}

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