제출 #1140507

#제출 시각아이디문제언어결과실행 시간메모리
1140507SyedSohaib_123Toy (CEOI24_toy)C++20
0 / 100
3 ms2632 KiB
#include <bits/stdc++.h>

using namespace std;

#define append push_back
#define int long long

const int N=4e5+10,LG=17;
int mod=998244353;

void solve(int tst){
    int n,m,k,l;
    cin>>n>>m>>k>>l;
    swap(n,m);
    int a,b,c,D;
    cin>>b>>a>>D>>c;
    a++;b++;
    c++;D++;
    int x=a,y=D;
    vector<string>v(n+2,string(m+2,'X'));
    for(int i=1;i<=n;i++){
        cin>>v[i];
        v[i]="X"+v[i]+"X";
    }
    vector<vector<int>>dx(n+2,vector<int>(m+2)),dy=dx,ps=dx;
    for(int i=0;i<=n+1;i++){
        vector<int>t(m+2,0);
        int l=0;
        for(int j=0;j<=m+1;j++){
            if(v[i][j]=='X') l=j;
            t[j]=l;
        }
        l=m+1;
        for(int j=m+1;j+1;j--){
            if(v[i][j]=='X') l=j;
            dx[i][j]=l-t[j]-1;
        }
    }
    for(int i=0;i<=m+1;i++){
        vector<int>t(n+2,0);
        int l=0;
        for(int j=0;j<=n+1;j++){
            if(v[j][i]=='X') l=j;
            t[j]=l;
        }
        l=n+1;
        for(int j=n+1;j+1;j--){
            if(v[j][i]=='X') l=j;
            dy[j][i]=l-t[j]-1;
        }
    }
    // K -> j
    ps[x][y]=1;
    deque<pair<int,int>>d;
    d.append({x,y});
    while(d.size()){
        auto [X,Y]=d[0];
        d.pop_front();
        if(v[X-1][Y]!='X' and !ps[X-1][Y] and dy[X-1][Y]>=l and dx[X-1][Y]>=k){
            ps[X-1][Y]=1;
            d.append({X-1,Y});
        }
        if(v[X+1][Y]!='X' and !ps[X+1][Y] and dy[X+1][Y]>=l and dx[X+1][Y]>=k){
            ps[X+1][Y]=1;
            d.append({X+1,Y});
        }
        if(v[X][Y-1]!='X' and !ps[X][Y-1] and dy[X][Y-1]>=l and dx[X][Y-1]>=k){
            ps[X][Y-1]=1;
            d.append({X,Y-1});
        }
        if(v[X][Y+1]!='X' and !ps[X][Y+1] and dy[X][Y+1]>=l and dx[X][Y+1]>=k){
            ps[X][Y+1]=1;
            d.append({X,Y+1});
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ps[i][j] and v[i][j]=='*'){
                cout<<"YES"<<endl;return;
            }
        }
    }
    cout<<"NO"<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}
#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...