제출 #1365520

#제출 시각아이디문제언어결과실행 시간메모리
1365520lucasdmyToy (CEOI24_toy)C++20
100 / 100
170 ms188316 KiB
#include <bits/stdc++.h>
using namespace std;
const int MAXN=1510;
int n, m, w, h;
int v[MAXN][MAXN], marc[MAXN][MAXN];
vector<int>b_line[MAXN], b_col[MAXN];
void dfs(int l, int c){
    marc[l][c]=1;
    if(l!=n and marc[l+1][c]==0){
        int aux=*prev(lower_bound(b_line[l].begin(), b_line[l].end(), c)), aux2=*prev(upper_bound(b_line[l+1].begin(), b_line[l+1].end(), c));
        int mn=max(aux, aux2);
        aux=*lower_bound(b_line[l].begin(), b_line[l].end(), c), aux2=*lower_bound(b_line[l+1].begin(), b_line[l+1].end(), c);
        int mx=min(aux, aux2);
        if(mx-mn-1>=w){
            dfs(l+1, c);
        }
    }
    if(l!=1 and marc[l-1][c]==0){
        int aux=*prev(lower_bound(b_line[l].begin(), b_line[l].end(), c)), aux2=*prev(upper_bound(b_line[l-1].begin(), b_line[l-1].end(), c));
        int mn=max(aux, aux2);
        aux=*lower_bound(b_line[l].begin(), b_line[l].end(), c), aux2=*lower_bound(b_line[l-1].begin(), b_line[l-1].end(), c);
        int mx=min(aux, aux2);
        if(mx-mn-1>=w){
            dfs(l-1, c);
        }
    }
    if(c!=m and marc[l][c+1]==0){
        int aux=*prev(lower_bound(b_col[c].begin(), b_col[c].end(), l)), aux2=*prev(upper_bound(b_col[c+1].begin(), b_col[c+1].end(), l));
        int mn=max(aux, aux2);
        aux=*lower_bound(b_col[c].begin(), b_col[c].end(), l), aux2=*lower_bound(b_col[c+1].begin(), b_col[c+1].end(), l);
        int mx=min(aux, aux2);
        if(mx-mn-1>=h){
            dfs(l, c+1);
        }
    }
    if(c!=1 and marc[l][c-1]==0){
        int aux=*prev(lower_bound(b_col[c].begin(), b_col[c].end(), l)), aux2=*prev(upper_bound(b_col[c-1].begin(), b_col[c-1].end(), l));
        int mn=max(aux, aux2);
        aux=*lower_bound(b_col[c].begin(), b_col[c].end(), l), aux2=*lower_bound(b_col[c-1].begin(), b_col[c-1].end(), l);
        int mx=min(aux, aux2);
        if(mx-mn-1>=h){
            dfs(l, c-1);
        }
    }
}
int main(){
    int ch, lh, cv, lv;
    cin>>m>>n>>w>>h>>ch>>lh>>cv>>lv;
    int fx, fy;
    for(int k=1;k<=m;k++){
        b_col[k].push_back(0);
    }
    for(int k=1;k<=n;k++){
        b_line[k].push_back(0);
        for(int i=1;i<=m;i++){
            char c;
            cin>>c;
            if(c=='X'){
                v[k][i]=1;
                b_line[k].push_back(i);
                b_col[i].push_back(k);
            }else if(c=='*'){
                fx=k, fy=i;
            }
        }
        b_line[k].push_back(m+1);
    }
    for(int k=1;k<=m;k++){
        b_col[k].push_back(n+1);
    }
    dfs(lh+1, cv+1);
    if(marc[fx][fy]){
        cout<<"YES";;
    }else{
        cout<<"NO";
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…