제출 #1342763

#제출 시각아이디문제언어결과실행 시간메모리
1342763po_rag526Toy (CEOI24_toy)C++20
14 / 100
1598 ms110364 KiB
//Valeriannn
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define endl '\n'
#define Valerian void
#define Valerian_or_Habil ios::sync_with_stdio(false); cin.tie(0);

using namespace std;

int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};

Valerian solve(){
    int W,H,K,L;
    cin>>W>>H>>K>>L;

    int hx,hy,vx,vy;
    cin>>hx>>hy>>vx>>vy;

    vector<string> g(H);
    for(int i=0;i<H;i++) cin>>g[i];

    int tx=-1,ty=-1;
    for(int i=0;i<H;i++)
        for(int j=0;j<W;j++)
            if(g[i][j]=='*') ty=i,tx=j;

    map<vector<int>,int> dist;
    queue<vector<int>> q;

    q.push({hx,hy,vx,vy});
    dist[{hx,hy,vx,vy}]=0;

    while(!q.empty()){
        vector<int> cur=q.front(); q.pop();
        int xh=cur[0], yh=cur[1], xv=cur[2], yv=cur[3];
        int d=dist[cur];

        int cx=xv, cy=yh;
        if(cx==tx && cy==ty){
            cout<<"YES"<<endl;
            return;
        }

        for(int i=0;i<4;i++){
            int nxh=xh+dx[i], nyh=yh+dy[i];
            if(nxh>=0 && nxh+K-1<W && nyh>=0 && nyh<H){
                int ok=1;
                for(int j=0;j<K;j++) if(g[nyh][nxh+j]=='X') ok=0;
                if(ok){
                    int ix=xv, iy=nyh;
                    if(ix>=nxh && ix<=nxh+K-1 && iy>=yv && iy<=yv+L-1){
                        vector<int> nxt={nxh,nyh,xv,yv};
                        if(!dist.count(nxt)){
                            dist[nxt]=d+1;
                            q.push(nxt);
                        }
                    }
                }
            }
        }

        for(int i=0;i<4;i++){
            int nxv=xv+dx[i], nyv=yv+dy[i];
            if(nxv>=0 && nxv<W && nyv>=0 && nyv+L-1<H){
                int ok=1;
                for(int j=0;j<L;j++) if(g[nyv+j][nxv]=='X') ok=0;
                if(ok){
                    int ix=nxv, iy=yh;
                    if(ix>=xh && ix<=xh+K-1 && iy>=nyv && iy<=nyv+L-1){
                        vector<int> nxt={xh,yh,nxv,nyv};
                        if(!dist.count(nxt)){
                            dist[nxt]=d+1;
                            q.push(nxt);
                        }
                    }
                }
            }
        }
    }

    cout<<"NO"<<endl;
}

int main(){
    Valerian_or_Habil;
    solve();
}
#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...