Submission #1235353

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235353		laurra	Toy (CEOI24_toy)	C++20	100 / 100	220 ms	187708 KiB

Main

#include <iostream>

using namespace std;

struct coordonata
{
    int x,y;
};
#define dim 1505
int a[dim][dim],st[dim][dim],dr[dim][dim],jos[dim][dim],sus[dim][dim];
int W,H,K,L;
bool viz[dim][dim];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
bool ok(int x,int y)
{
    if(x>=0 && x<H && y>=0 && y<W)
        return true;
    return false;
}
bool transfer(int x,int y,int xn,int yn)
{
    if(y==yn)
    {
        ///Orizontal
        int mini,maxi;
        maxi=max(st[x][y]+1,st[xn][yn]+1);
        mini=min(dr[x][y],dr[xn][yn]);
        if(mini-maxi>=K)
            return true;
        return false;
    }
    else
    {
        ///Vertical
        int mini,maxi;
        maxi=max(sus[x][y]+1,sus[xn][yn]+1);
        mini=min(jos[x][y],jos[xn][yn]);
        if(mini-maxi>=L)
            return true;
        return false;
    }
}
void parcurgere(int x,int y)
{
    int xn,yn;
    viz[x][y]=1;
    for(int i=0;i<4;i++)
    {
        xn=x+dx[i];
        yn=y+dy[i];
        if(ok(xn,yn)==true && viz[xn][yn]==0 && a[xn][yn]==0 && transfer(x,y,xn,yn)==true)
        {
            parcurgere(xn,yn);
        }
    }
}
void init()
{
    int i,poz,j;
    for(i=0;i<H;i++)
    {
        poz=-1;
        for(j=0;j<W;j++)
        {
            if(a[i][j]==1)
                poz=j;
            st[i][j]=poz;
        }
        poz=W;
        for(j=W-1;j>=0;j--)
        {
            if(a[i][j]==1)
                poz=j;
            dr[i][j]=poz;
        }
    }
    for(j=0;j<W;j++)
    {
        poz=-1;
        for(i=0;i<H;i++)
        {
            if(a[i][j]==1)
                poz=i;
            sus[i][j]=poz;
        }
        poz=H;
        for(i=H-1;i>=0;i--)
        {
            if(a[i][j]==1)
                poz=i;
            jos[i][j]=poz;
        }
    }
}

int main()
{
    coordonata h,v,target,intersectie;
    int i,j;
    string s;
    cin>>W>>H>>K>>L;
    cin>>h.x>>h.y>>v.x>>v.y;
    for(i=0;i<H;i++)
    {
        cin>>s;
        for(j=0;j<s.length();j++)
        {
            if(s[j]=='.')
            {
                a[i][j]=0;
            }
            else if(s[j]=='X')
            {
                a[i][j]=1;
            }
            else
            {
                a[i][j]=0;
                target.x=i;
                target.y=j;
            }
        }
    }
    init();
    intersectie.x=h.y;
    intersectie.y=v.x;
    parcurgere(intersectie.x,intersectie.y);
    if(viz[target.x][target.y]==0)
        cout<<"NO";
    else
        cout<<"YES";
    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