제출 #1365479

#제출 시각아이디문제언어결과실행 시간메모리
1365479talyToy (CEOI24_toy)C++20
0 / 100
5 ms4124 KiB
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define all(x) (x).begin(),(n).end()


signed main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m, k, l; cin >> n >> m >> k >> l;
    swap(n, m);
    vector<vector<char> > mat(n, vector<char>(m));
    int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
    swap(x1, y1);
    swap(x2, y2);
    int qx=0, qy=0;
    vector<vector<int> > num_ver, num_hor, pas_ver, pas_hor;
    num_ver.resize(n, vector<int>(m));
    num_hor.resize(n, vector<int>(m));
    pas_ver.resize(n, vector<int>(m));
    pas_hor.resize(n, vector<int>(m));
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> mat[i][j];
            if(mat[i][j]=='X'){
                num_ver[i][j]=0;
                num_hor[i][j]=0;
            }
            else{
                if(mat[i][j]=='*'){
                    qx=i;
                    qy=j;
                }
                if(i==0){
                    num_ver[i][j]=1;
                }else{
                    num_ver[i][j]=num_ver[i-1][j]+1;
                }
                if(j==0){
                    num_hor[i][j]=1;
                }else{
                    num_hor[i][j]=num_hor[i][j-1]+1;
                }
            }
        }
    }
    // for(int i=0; i<n; i++){
    //     for(int j=0; j<m; j++){
    //         cout << num_ver[i][j];
    //     }
    //     cout << endl;
    // }
    queue<pii> q1;
    //vector<pii> viz = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    vector<pair<int, int> > viz;
    viz.push_back(make_pair(0LL, 1LL));
    viz.push_back(make_pair(0LL, -1LL));
    viz.push_back(make_pair(-1LL, 0LL));
    viz.push_back(make_pair(1LL, 0LL));
    q1.push({x1, y1+k-1});
    pas_hor[x1][y1+k-1]=1;
    while(!q1.empty()){
        int x=q1.front().first;
        int y=q1.front().second;
        //cout << x << " "<<y<<endl;
        q1.pop();
        for(int j=0; j<4; j++){
            pii p=viz[j];
            int ax=p.first;
            int ay=p.second;
            int nx=x+ax;
            int ny=y+ay;
       // cout << nx << " "<<ny<<" "<<num_hor[nx][ny] <<endl;
            if(nx>=0&&ny>=0&&nx<n&&ny<m&&!pas_hor[nx][ny]&&num_hor[nx][ny]>=k){
                q1.push({nx, ny});
                pas_hor[nx][ny]=1;
            }
        }
    }
    queue<pii> q2;
    q2.push({x2+l-1, y2});
    pas_ver[x2+l-1][y2]=1;
    while(!q2.empty()){
        int x=q2.front().first;
        int y=q2.front().second;
        //cout << x << " "<<y<<endl;
        q2.pop();
        for(int j=0; j<4; j++){
            pii p=viz[j];
            int ax=p.first;
            int ay=p.second;
            int nx=x+ax;
            int ny=y+ay;
            if(nx>=0&&ny>=0&&nx<n&&ny<m&&!pas_ver[nx][ny]&&num_ver[nx][ny]>=l){
                q2.push({nx, ny});
                pas_ver[nx][ny]=1;
            }
        }
    }
    for(int i=n-1; i>=0; i--){
        for(int j=m-1; j>=0; j--){
            if(mat[i][j]=='X'){
                pas_ver[i][j]=0;
                pas_hor[i][j]=0;
            }else{
                if(j<m-1){
                    pas_hor[i][j]=max(pas_hor[i][j+1], pas_hor[i][j]);
                }
                if(i<n-1){
                    pas_ver[i][j]=max(pas_ver[i+1][j], pas_ver[i][j]);
                }
            }
        }
    }
    // for(int i=0; i<n; i++){
    //     for(int j=0; j<m; j++){
    //         cout << pas_hor[i][j];
    //     }
    //     cout << endl;
    // }
    //cout << 1 << endl;
    vector<vector<int> > marc(n, vector<int>(m));
    queue<pii> pos;
    pos.push({x1, y2});
    marc[x1][y2]=1;
    while(!pos.empty()){
        int x=pos.front().first;
        int y=pos.front().second;
        pos.pop();
        for(int j=0; j<4; j++){
            pii p=viz[j];
            int ax=p.first;
            int ay=p.second;
            int nx=x+ax;
            int ny=y+ay;
            if(nx>=0&&ny>=0&&nx<n&&ny<m&&!marc[nx][ny]&&pas_ver[nx][ny]&&pas_hor[nx][ny]){
                pos.push({nx, ny});
                marc[nx][ny]=1;
            }
        }
    }
    if(marc[qx][qy]){
        cout << "YES"<<endl;
    }else{
        cout << "NO"<<endl;
    }
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…