제출 #1364998

#제출 시각아이디문제언어결과실행 시간메모리
1364998lucasdmyToy (CEOI24_toy)C++20
0 / 100
1528 ms1114112 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1510;
int n, m, w, h;
int marc[MAXN][MAXN], v[MAXN][MAXN], scol[MAXN][MAXN], sline[MAXN][MAXN];
void dfs(int l, int c, int top_vert, int left_hor){
    stack<pair<pair<int, int>, pair<int, int>>>s;
    s.push({{l, c}, {top_vert, left_hor}});
    marc[l][c]=1;
    while(!s.empty()){
        l=s.top().first.first, c=s.top().first.second, top_vert=s.top().second.first, left_hor=s.top().second.second;
        s.pop();
        if(c!=n-1 and marc[l][c+1]==0){
            if(left_hor+w-1!=c and scol[c+1][top_vert]==scol[c+1][top_vert+h-1] and v[top_vert][c+1]==0){
                s.push({{l, c+1}, {top_vert, left_hor}});
                marc[l][c+1]=1;
            }
            if(left_hor+w-1!=n-1 and v[l][left_hor+w]==0 and c!=left_hor){
                s.push({{l, c}, {top_vert, left_hor+1}});
            }
        }
        if(c!=0 and marc[l][c-1]==0){
            if(left_hor!=c and scol[c-1][top_vert]==scol[c-1][top_vert+h-1] and v[top_vert][c-1]==0){
                s.push({{l, c-1}, {top_vert, left_hor}});
                marc[l][c-1]=1;
            }else if(left_hor!=0 and v[l][left_hor-1]==0 and c!=left_hor+h-1){
                s.push({{l, c}, {top_vert, left_hor-1}});
            }
        }
        if(l!=m-1 and marc[l+1][c]==0){
            if(top_vert+h-1!=l and sline[l+1][left_hor]==sline[l+1][left_hor+w-1] and v[l+1][left_hor]==0){
                s.push({{l+1, c}, {top_vert, left_hor}});
                marc[l+1][c]=1;
            }else if(top_vert+h-1!=m-1 and v[top_vert+h][c]==0 and l!=top_vert){
                s.push({{l, c}, {top_vert+1, left_hor}});
            }
        }
        if(l!=0 and marc[l-1][c]==0){
            if(top_vert!=l and sline[l-1][left_hor]==sline[l-1][left_hor+w-1] and v[l-1][left_hor]==0){
                s.push({{l-1, c}, {top_vert, left_hor}});
                marc[l-1][c]=1;
            }else if(top_vert!=0 and v[top_vert-1][c]==0 and l!=top_vert+w-1){
                s.push({{l, c}, {top_vert-1, left_hor}});
            }
        }
    }
}
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];
            }
        }
    }
    dfs(yh, xv, yv, xh);
    if(marc[fx][fy]){
        cout<<"YES";
    }else{
        cout<<"NO";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…