Submission #1346426

#TimeUsernameProblemLanguageResultExecution timeMemory
1346426MrAndriaToy (CEOI24_toy)C++20
0 / 100
110 ms151984 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
int n,m,a[5],lef[365][365],righ[365][365];
char ch[365][365];
int k,L,pref[365][365];
bool vis[365][365][365];
int calc(int x,int y,int a,int b){
    return pref[a][b]-pref[x-1][b]-pref[a][y-1]+pref[x-1][y-1];
}
int sz(int x,int y,int a,int b){
    return min(righ[x][y],righ[a][b])-max(lef[x][y],lef[a][b])+1;
}
void dfs(int x,int y,int z){
    // cout<<x<<" "<<y<<" "<<z<<endl;
    if(x>n or x<1 or y<1 or y>m or z<0 or z>L-1){
        // cout<<x<<" "<<y<<" x "<<z<<endl;
        
        // return;
        assert(0);
    }
    vis[x][y][z]=1;
    if(z+1<=L-1 and sz(x+z,y,x+z+1,y)>=k and !vis[x][y][z+1]){
        dfs(x,y,z+1);
    }
    if(z-1>=0 and sz(x+z-1,y,x+z,y)>=k and !vis[x][y][z-1]){
        dfs(x,y,z-1);
    }
    if(x+L<=n and z!=0 and ch[x+L][y]!='X' and !vis[x+1][y][z-1]){
        dfs(x+1,y,z-1);
    }
    if(x-1>=1 and z!=L-1 and ch[x-1][y]!='X' and !vis[x-1][y][z+1]){
        if(x==2 and y==2 and z==2)cout<<"HERE"<<endl;
        dfs(x-1,y,z+1);
    }
    if(y+1<=m and calc(x,y+1,x+L-1,y+1)==0 and !vis[x][y+1][z]){
        dfs(x,y+1,z);
    }
    if(y-1>=1 and calc(x,y-1,x+L-1,y-1)==0 and !vis[x][y-1][z]){
        dfs(x,y-1,z);
    }
}
int main(){
    cin>>m>>n>>k>>L;
    cin>>a[2]>>a[1];
    a[2]++;
    a[1]++;
    cin>>a[4]>>a[3];
    a[4]++;
    a[3]++;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch[i][j];
            
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(ch[i][j]=='*');
        } 
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            lef[i][j]=-1;
            righ[i][j]=-1;    
            for(int k=j;k>=1;k--){
                if(ch[i][k]=='X'){
                    break;
                }
                lef[i][j]=k;
            }
            for(int k=j;k<=m;k++){
                if(ch[i][k]=='X'){
                    break;
                }
                righ[i][j]=k;
            }
        }
    }
    dfs(a[3],a[4],a[1]-a[3]-1);
    int x,y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ch[i][j]=='*'){
                x=i;
                y=j;

            }
        }
    }
    for(int i=1;i<=x;i++){
        if(vis[i][y][x-i]){
            cout<<"YES"<<endl;
            return 0;
        }
    }
    cout<<"NO"<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...