제출 #1364942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364942		Sofiatpc	Toy (CEOI24_toy)	C++20	100 / 100	471 ms	379616 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
const int MAXN = 1505;
vector<int> vi[MAXN][MAXN], vj[MAXN][MAXN];
int mat[MAXN][MAXN], prv[MAXN][MAXN], nxt[MAXN][MAXN], marc[MAXN][MAXN];

void dfs(int i, int j){
    if(mat[i][j] || marc[i][j])return;

    marc[i][j] = 1;
    for(int k = 0; k < sz(vi[i][j]); k++) dfs(vi[i][j][k], vj[i][j][k]);
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n,m,K,L; cin>>m>>n>>K>>L;
    int ih,jh,iv,jv; cin>>jh>>ih>>jv>>iv;

    int fimi, fimj;
    for(int i = 0; i < n; i++){
        string s; cin>>s;
        for(int j = 0; j < m; j++){
            if(s[j] == 'X')mat[i][j] = 1;
            else if(s[j] == '*'){fimi = i; fimj = j;}
        }
    }

    for(int j = 0; j < m; j++){
        for(int i = 0; i < n; i++){
            if(mat[i][j])prv[i][j] = i+1;
            else if(i == 0)prv[i][j] = 0;
            else prv[i][j] = prv[i-1][j];
        }

        for(int i = n-1; i >= 0; i--){
            if(mat[i][j])nxt[i][j] = i-1;
            else if(i == n-1)nxt[i][j] = n-1;
            else nxt[i][j] = nxt[i+1][j];
        }
    }

    int dif[2] = {-1,1};
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            for(int d = 0; d < 2; d++){
                int vizi = i, vizj = j+dif[d];

                if(vizj < 0 || vizj >= m || mat[vizi][vizj])continue;

                if( max(prv[i][j], i-L+1) <= min(nxt[vizi][vizj]-L+1, i) 
                && max(prv[vizi][vizj], i-L+1) <= min(nxt[i][j]-L+1, i) 
                && max(prv[i][j], i-L+1) <= min(nxt[i][j]-L+1, i) 
                && max(prv[vizi][vizj], i-L+1) <= min(nxt[vizi][vizj]-L+1, i) ){
                    vi[i][j].push_back(vizi); vj[i][j].push_back(vizj);
                }
            }

    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(mat[i][j])prv[i][j] = j+1;
            else if(j == 0)prv[i][j] = 0;
            else prv[i][j] = prv[i][j-1];
        }

        for(int j = m-1; j >= 0; j--){
            if(mat[i][j])nxt[i][j] = j-1;
            else if(j == m-1)nxt[i][j] = m-1;
            else nxt[i][j] = nxt[i][j+1];
        }
    }

    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            for(int d = 0; d < 2; d++){
                int vizi = i+dif[d], vizj = j;

                if(vizi < 0 || vizi >= n || mat[vizi][vizj])continue;

                if( max(prv[i][j], j-K+1) <= min(nxt[vizi][vizj]-K+1, j) 
                && max(prv[vizi][vizj], j-K+1) <= min(nxt[i][j]-K+1, j) 
                && max(prv[i][j], j-K+1) <= min(nxt[i][j]-K+1, j) 
                && max(prv[vizi][vizj], j-K+1) <= min(nxt[vizi][vizj]-K+1, j) ){
                    vi[i][j].push_back(vizi); vj[i][j].push_back(vizj);
                }
            }
        
    dfs(ih, jv);

    if(marc[fimi][fimj])cout<<"YES\n";
    else cout<<"NO\n";
        
}

• 서브태스크 0: 0 / 0
• 서브태스크 1: 14 / 14
• 서브태스크 2: 21 / 21
• 서브태스크 3: 9 / 9
• 서브태스크 4: 29 / 29
• 서브태스크 5: 27 / 27