Submission #1364993

#TimeUsernameProblemLanguageResultExecution timeMemory
1364993lucasdmyToy (CEOI24_toy)C++20
0 / 100
11 ms18616 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1510;
int n, m, w, h;
int marc1[MAXN][MAXN], marc2[MAXN][MAXN], v[MAXN][MAXN], scol[MAXN][MAXN], sline[MAXN][MAXN];
void dfs1(int col, int lst, int lend){
    while(0<=lst and v[lst][col]==0){
        lst--;
    }
    if(lst<0 or v[lst][col]){
        lst++;
    }
    while(lend<m and v[lend][col]==0){
        lend++;
    }
    if(lend>=m or v[lend][col]){
        lend--;
    }
    for(int k=lst;k<=lend;k++){
        marc1[k][col]=1;
    }
    for(int k=lst;k<=lend-h+1;k++){
        if(col!=n-1 and scol[col+1][k]==scol[col+1][k+h-1] and v[k][col+1]==0 and marc1[k][col+1]==0){
            dfs1(col+1, k, k+h-1);
        }
        if(col!=0 and scol[col-1][k]==scol[col-1][k+h-1] and v[k][col-1]==0 and marc1[k][col-1]==0){
            dfs1(col-1, k, k+h-1);
        }
    }
}
void dfs2(int line, int cst, int cend){
    while(0<=cst and v[line][cst]==0){
        cst--;
    }
    if(cst<0 or v[line][cst]){
        cst++;
    }
    while(cend<n and v[line][cend]==0){
        cend++;
    }
    if(cend>=n or v[line][cend]){
        cend--;
    }
    for(int k=cst;k<=cend;k++){
        marc2[line][k]=1;
    }
    for(int k=cst;k<=cend-w+1;k++){
        if(line!=m-1 and sline[line+1][k]==sline[line+1][k+w-1] and v[line+1][k]==0 and marc2[line+1][k]==0){
            dfs2(line+1, k, k+w-1);
        }
        if(line!=0 and sline[line-1][k]==sline[line-1][k+w-1] and v[line-1][k]==0 and marc2[line-1][k]==0){
            dfs2(line-1, k, k+w-1);
        }
    }
}
int marc3[MAXN][MAXN];
void dfs3(int l, int c){
    marc3[l][c]=1;
    if(l!=m-1 and marc3[l+1][c]==0 and marc1[l+1][c]==1 and marc2[l+1][c]==1){
        dfs3(l+1, c);
    }
    if(l!=0 and marc3[l-1][c]==0 and marc1[l-1][c]==1 and marc2[l-1][c]==1){
        dfs3(l-1, c);
    }
    if(c!=n-1 and marc3[l][c+1]==0 and marc1[l][c+1]==1 and marc2[l][c+1]==1){
        dfs3(l, c+1);
    }
    if(c!=0 and marc3[l][c-1]==0 and marc1[l][c-1]==1 and marc2[l][c-1]==1){
        dfs3(l, c-1);
    }
}
int main(){
    cin>>n>>m>>w>>h;
    int xh, yh, xv, yv;
    cin>>xh>>yh>>xv>>yv;
    int fx, fy;
    for(int k=0;k<m;k++){
        for(int i=0;i<n;i++){
            char c;
            cin>>c;
            if(c=='X'){
                v[k][i]=1;
                sline[k][i]=1+sline[k][i-1];
                scol[i][k]=1+scol[i][k-1];
            }else if(c=='*'){
                fx=k, fy=i;
                sline[k][i]=sline[k][i-1];
                scol[i][k]=scol[i][k-1];
            }else{
                sline[k][i]=sline[k][i-1];
                scol[i][k]=scol[i][k-1];
            }
        }
    }
    dfs1(xv, yv, yv+h-1);
    dfs2(yh, xh, xh+w-1);
    dfs3(yh, xv);
    if(marc3[fx][fy]){
        cout<<"YES";
    }else{
        cout<<"NO";
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...