Submission #1232080

#	Time	Username	Problem	Language	Result	Execution time	Memory
1232080		jaskier	Toy (CEOI24_toy)	C++20	100 / 100	291 ms	191036 KiB

Main

#include<bits/stdc++.h>

using namespace std;

const int maxn=1509;
int tab[maxn][maxn], szerokosc, wysokosc, kraw[maxn][maxn][5], w, k, lewo[maxn][maxn], prawo[maxn][maxn], gora[maxn][maxn], dol[maxn][maxn];
bool odw[maxn][maxn];
vector<pair<int, int>> ruza={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

void stworz(int a, int b) {
    int l, p, L, P, g, d, G, D;
    if(a!=1) {
        l=lewo[a][b];
        p=prawo[a][b];
        L=lewo[a-1][b];
        P=prawo[a-1][b];
        if(min(p, P)-max(l, L)-1 >= szerokosc){
            kraw[a][b][0]=1;
        }
    }
    if(a!=w) {
        l=lewo[a][b];
        p=prawo[a][b];
        L=lewo[a+1][b];
        P=prawo[a+1][b];
        if(min(p, P)-max(l, L)-1 >= szerokosc){
            kraw[a][b][1]=1;
        }
    }
    if(b!=1) {
        d=dol[a][b];
        g=gora[a][b];
        D=dol[a][b-1];
        G=gora[a][b-1];
        if(min(d, D)-max(g, G)-1 >= wysokosc) {
            kraw[a][b][2]=1;
        }
    }
    if(b!=k) {
        d=dol[a][b];
        g=gora[a][b];
        D=dol[a][b+1];
        G=gora[a][b+1];
        if(min(d, D)-max(g, G)-1 >= wysokosc) {
            kraw[a][b][3]=1;
        }
    }
}

void DFS(int a, int b) {
    odw[a][b]=1;
    int na, nb;
    for(int i=0; i<4; i++) {
        if(kraw[a][b][i]==0) {
            continue;
        }
        na=a+ruza[i].first;
        nb=b+ruza[i].second;
        if(!odw[na][nb]) {
            DFS(na, nb);
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int a, b, c, d, finalnyx, finalnyy;
    cin >> k >> w >> szerokosc >> wysokosc;
    cin >> b >> a;
    cin >> d >> c;
    b++;
    a++;
    d++;
    c++;
    char x;
    for(int i=1; i<=w; i++) {
        for(int j=1; j<=k; j++) {
            cin >> x;
            if(x=='X') {
                tab[i][j]=1;
            }
            else if(x=='*') {
                finalnyx=i;
                finalnyy=j;
            }
        }
    }
    int ziomo;
    for(int i=1; i<=w; i++) {
        prawo[i][k+1]=k+1;
        for(int j=1; j<=k; j++) {
            ziomo=k-j+1;
            lewo[i][j]=lewo[i][j-1];
            prawo[i][ziomo]=prawo[i][ziomo+1];
            if(tab[i][j]==1) {
                lewo[i][j]=j;
            }
            if(tab[i][ziomo]==1) {
                prawo[i][ziomo]=ziomo;
            }
        }
    }
    for(int j=1; j<=k; j++) {
        dol[w+1][j]=w+1;
        for(int i=1; i<=w; i++) {
            ziomo=w-i+1;
            gora[i][j]=gora[i-1][j];
            dol[ziomo][j]=dol[ziomo+1][j];
            if(tab[i][j]==1) {
                gora[i][j]=i;
            }
            if(tab[ziomo][j]==1) {
                dol[ziomo][j]=ziomo;
            }
        }
    }

    for(int i=1; i<=w; i++) {
        for(int j=1; j<=k; j++) {
            stworz(i, j);
           // cout << "DLA: " << i << ' ' << j << "  :  " << kraw[i][j][0] << ' ' << kraw[i][j][1] << ' ' << kraw[i][j][2] << ' ' << kraw[i][j][3] << endl;
        }
    }
    DFS(a, d);
    if(odw[finalnyx][finalnyy]) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO";
    }
}
/*
4 3 3 2
0 1 0 0
.X.*
....
...X
*/

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