제출 #1232062

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232062		AlperenT_	Toy (CEOI24_toy)	C++20	100 / 100	219 ms	194380 KiB

Main

#include <bits/stdc++.h> 
#pragma GCC optimize("O3,unroll-loops") 
#define pb push_back
#define F first
#define pii pair<ll,ll> 
#define all(a) a.begin(),a.end()
#define S second 
#define sz(a) (int)a.size()
#define rep(i , a , b) for(int i = (a) ; i <= (b) ; i++)
#define per(i , a , b) for(int i = (a) ; i >= (b) ; i--)
#define ld double
#define ll long long
using namespace std ;
const int maxn = 2000  + 10, inf = 1e9+ 10 , mod = 1e9 + 9 ;
char c[maxn][maxn] ;
int le[maxn][maxn],ri[maxn][maxn] , dw[maxn][maxn] , up[maxn][maxn] ;
bool mark[maxn][maxn] ;
int dx[] = {1,-1,0,0} , dy[] = {0,0,-1,1} ;
int n , m , k, l ;
void dfs(int x, int y){
    mark[x][y] =1 ;//cout << x << " " << y << "<-\n"; 
    rep(i , 0, 3){
        int a= dx[i] + x , b = dy[i] + y ;
        if(mark[a][b] ==1 || a <= 0  || a > n || b <= 0 || b > m || c[a][b]== 'X')continue ;
        if(i <= 1){
            if(min(le[x][y] , le[a][b]) + min(ri[x][y] , ri[a][b])-1 >= k){
                dfs(a,b) ;
            }
        }else{
            if(min(up[x][y] , up[a][b]) + min(dw[x][y] , dw[a][b])-1 >= l){
                dfs(a,b) ;
            }       
       }
    }
}


signed main(){
    ios_base::sync_with_stdio(0) ; cin.tie(0) ;
     cin >> n >> m >> k >> l ;// 1 x  k
     swap(n , m);
    int x0 , y0 , x1 ,y1  ;
    cin >> x0 >> y0 >> x1 >> y1 ;
    x0++;y0++;x1++;y1++;
    swap(x0 , y0 );
    swap(x1 ,y1) ;
    int i1, j1 ;
    rep(i ,1, n){
        rep(j ,1 , m){
            cin >> c[i][j] ;
            if(c[i][j] == '*'){
                i1 = i ; j1 = j ;
            }
        }
    }
    rep(i ,1 ,n){
        rep(j ,1 ,m){
            if(c[i][j] == 'X'){
                le[i][j] = 0;
            }else{
                le[i][j] = le[i][j-1] + 1; 
            }
        }
    }
    rep(i ,1, n){
        per(j , m , 1){
            if(c[i][j] == 'X'){
                ri[i][j] = 0 ;
            }else{
                ri[i][j] = ri[i][j+1] + 1; 
            }
        }
    }
    rep(j ,1 ,m){
        rep(i , 1 ,n){
            if(c[i][j] == 'X'){
                up[i][j] = 0;
            }else{
                up[i][j] = up[i-1][j] + 1;
            }
        }
    }
    rep(j ,1 ,m){
        per(i , n ,1 ){
            if(c[i][j] == 'X'){
                dw[i][j] = 0;
            }else{
                dw[i][j] = dw[i+1][j] + 1;
            }
        }
    }
    int x= x0 ,y =  y1 ;
    dfs(x,y) ;
    if(mark[i1][j1] == 1){
        cout << "YES\n";
    }else{
        cout << "NO\n"; 
    }
}
/*
*/

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27