Submission #1070137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070137		naneosmic	Toy (CEOI24_toy)	C++14	100 / 100	378 ms	286964 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
vector<vector<int>>najljevlji,najdesniji,najgornji,najdonji;
vector<vector<char>>grid;
int w,h,k,l,xh,yh,xv,yv,x,y;
vector<vector<bool>>visited;
void dfs(int x1,int y1){
    if(visited[x1][y1])return;
    visited[x1][y1]=true;
    if(grid[x1+1][y1]!='X'){
        if(najdesniji[x1+1][y1]<=najljevlji[x1+1][y1])
        if(!((najdesniji[x1][y1]>najljevlji[x1+1][y1])||(najdesniji[x1+1][y1]>najljevlji[x1][y1])))dfs(x1+1,y1);
    }
    if(grid[x1-1][y1]!='X'){
        if(najdesniji[x1-1][y1]<=najljevlji[x1-1][y1])
        if(!((najdesniji[x1][y1]>najljevlji[x1-1][y1])||(najdesniji[x1-1][y1]>najljevlji[x1][y1])))dfs(x1-1,y1);
    }
    if(grid[x1][y1+1]!='X'){
        if(najgornji[x1][y1+1]>=najdonji[x1][y1+1])
        if(!((najgornji[x1][y1]<najdonji[x1][y1+1])||(najgornji[x1][y1+1]<najdonji[x1][y1])))dfs(x1,y1+1);
    }
    if(grid[x1][y1-1]!='X'){
        if(najgornji[x1][y1-1]>=najdonji[x1][y1-1])
        if(!((najgornji[x1][y1]<najdonji[x1][y1-1])||(najgornji[x1][y1-1]<najdonji[x1][y1])))dfs(x1,y1-1);
    }
}
signed main(){
    cin>>w>>h>>k>>l>>xh>>yh>>xv>>yv;xh++;yh++;xv++;yv++;
    grid.resize(h+2,vector<char>(w+2,'X'));
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            cin>>grid[i][j];
            if(grid[i][j]=='*'){
                x=i;y=j;
            }
        }
    }
    visited.resize(h+2,vector<bool>(w+2,false));
    najljevlji.resize(h+2,vector<int>(w+2,k-1));
    najdesniji.resize(h+2,vector<int>(w+2,0));
    najdonji.resize(h+2,vector<int>(w+2,0));
    najgornji.resize(h+2,vector<int>(w+2,l-1));
    for(int i=0;i<h+2;i++){
        for(int j=0;j<w+2;j++){
            if(grid[i][j]=='X'){
                for(int num=0;num<k;num++){
                    if((j+num+1)<w+2){
                        if(grid[i][j+num+1]!='X')najljevlji[i][j+num+1]=num;
                        else break;
                    }else break;
                }
                for(int num=0;num<l;num++){
                    if((i+num+1)<h+2){
                        if(grid[i+num+1][j]!='X')najgornji[i+num+1][j]=num;
                        else break;
                    }else break;
                }
            }
        }
    }
    for(int i=h+1;i>=0;i--){
        for(int j=w+1;j>=0;j--){
            if(grid[i][j]=='X'){
                for(int num=0;num<k;num++){
                    if((j-num-1)>=0){
                        if(grid[i][j-num-1]!='X')najdesniji[i][j-num-1]=k-1-num;
                        else break;
                    }else break;
                }
                for(int num=0;num<l;num++){
                    if((i-num-1)>=0){
                        if(grid[i-num-1][j]!='X')najdonji[i-num-1][j]=l-1-num;
                        else break;
                    }else break;
                }
            }
        }
    }
    dfs(yh,xv);
    cout<<((visited[x][y]==true)?"YES\n":"NO\n");
}

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