제출 #1346450

#제출 시각아이디문제언어결과실행 시간메모리
1346450MrAndriaToy (CEOI24_toy)C++20
100 / 100
273 ms366044 KiB
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
//#define int long long
int n,m,a[5],lef[1505][1505],righ[1505][1505],up[1505][1505],down[1505][1505];
char ch[1505][1505];
int k,L,pref[1505][1505];
bool vis[1505][1505];
int calc(int x,int y,int a,int b){
    return pref[a][b]-pref[x-1][b]-pref[a][y-1]+pref[x-1][y-1];
}
int sz(int x,int y,int a,int b){
    return min(righ[x][y],righ[a][b])-max(lef[x][y],lef[a][b])+1;
}
int szu(int x,int y,int a,int b){
    return min(down[x][y],down[a][b])-max(up[x][y],up[a][b])+1;
}
void dfs(int x,int y){
    
    vis[x][y]=1;
    if(x+1<=n and !vis[x+1][y] and sz(x,y,x+1,y)>=k){
        dfs(x+1,y);
    }
    if(x-1>=1 and !vis[x-1][y] and sz(x,y,x-1,y)>=k){
        dfs(x-1,y);
    }
    if(y+1<=m and !vis[x][y+1] and szu(x,y,x,y+1)>=L){
        dfs(x,y+1);
    }
    if(y-1>=1 and !vis[x][y-1] and szu(x,y,x,y-1)>=L){
        dfs(x,y-1);
    }
    
}
int main(){
    cin>>m>>n>>k>>L;
    cin>>a[2]>>a[1];
    a[2]++;
    a[1]++;
    cin>>a[4]>>a[3];
    a[4]++;
    a[3]++;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>ch[i][j];
            
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            pref[i][j]=pref[i-1][j]+pref[i][j-1]-pref[i-1][j-1]+(ch[i][j]=='X');
        } 
    }
    for(int i=1;i<=n;i++){
        
        righ[i][0]=-1;
        lef[i][0]=-1;
        for(int j=1;j<=m;j++){
            if(ch[i][j]=='X'){
                lef[i][j]=-1;
                continue;
            }
            if(lef[i][j-1]==-1){
                lef[i][j]=j;
            }else{
                lef[i][j]=lef[i][j-1];                
            }
        }
        righ[i][m+1]=-1;
        lef[i][m+1]=-1;
        for(int j=m;j>=1;j--){
            if(ch[i][j]=='X'){
                righ[i][j]=-1;
                continue;
            }
            if(righ[i][j+1]==-1){
                righ[i][j]=j;
            }else{
                righ[i][j]=righ[i][j+1];                
            }
        }
    }
    for(int j=1;j<=m;j++){
        up[0][j]=-1;
        down[0][j]=-1;
        for(int i=1;i<=n;i++){
            if(ch[i][j]=='X'){
                up[i][j]=-1;
                continue;
            }
            if(up[i-1][j]==-1){
                up[i][j]=i;
            }else{
                up[i][j]=up[i-1][j];
            }
        }
        down[n+1][j]=-1;
        up[n+1][j]=-1;
        for(int i=n;i>=1;i--){
            if(ch[i][j]=='X'){
                down[i][j]=-1;
                continue;
            }
            if(down[i+1][j]==-1){
                down[i][j]=i;
            }else{
                down[i][j]=down[i+1][j];
            }
        }
    }
    dfs(a[1],a[4]);
    int x,y;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(ch[i][j]=='*'){
                x=i;
                y=j;

            }
        }
    }
    if(vis[x][y]){
        cout<<"YES"<<endl;
        return 0;
    }
    
    cout<<"NO"<<endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...