제출 #1342794

#제출 시각아이디문제언어결과실행 시간메모리
1342794vjudge1Toy (CEOI24_toy)C++20
100 / 100
405 ms386688 KiB
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#ifdef ULVI
    #include "debug.hpp"
#else
    #define db(...)
    #define dbv(v)
    #define line()
#endif
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define ff first
#define ss second
#define enld endl
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll sz=2e5+100;
const ll lg=20;
const ll mod=1e9+7;
const ll inf=1e18;
template<class T>
using indexed_set=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<vector<ll>> vis(2000,vector<ll>(2000));
ll n,m,k,l;
void dfs(ll x,ll y,vector<vector<array<ll,4>>> &bou){
    if(vis[x][y] || x>n || y>m || x<1 || y<1) return;
    vis[x][y]=1;
    if(min(bou[x][y][1],bou[x+1][y][1])-max(bou[x][y][0],bou[x+1][y][0])-1>=k) dfs(x+1,y,bou);
    if(min(bou[x][y][1],bou[x-1][y][1])-max(bou[x][y][0],bou[x-1][y][0])-1>=k) dfs(x-1,y,bou);
    if(min(bou[x][y][3],bou[x][y+1][3])-max(bou[x][y][2],bou[x][y+1][2])-1>=l) dfs(x,y+1,bou);
    if(min(bou[x][y][3],bou[x][y-1][3])-max(bou[x][y][2],bou[x][y-1][2])-1>=l) dfs(x,y-1,bou);
}

void solve(){
    ll x1,y1,x2,y2;
    cin>>m>>n>>k>>l;
    cin>>y1>>x1>>y2>>x2;
    y1++; x1++; y2++; x2++;
    vector<vector<char>> v(n+5,vector<char>(m+5));
    pll st;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            cin>>v[i][j];
            if(v[i][j]=='*') st={i,j};
        }
    }
    vector<vector<array<ll,4>>> bou(n+5,vector<array<ll,4>>(m+5));
    for(ll i=1;i<=n;i++) bou[i][m+1][1]=m+1;
    for(ll i=1;i<=m;i++) bou[n+1][i][3]=n+1;
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=m;j++){
            if(v[i][j]=='X') bou[i][j][0]=j;
            else bou[i][j][0]=bou[i][j-1][0];
        }
        for(ll j=m;j>=1;j--){
            if(v[i][j]=='X') bou[i][j][1]=j;
            else bou[i][j][1]=bou[i][j+1][1];
        }
    }
    for(ll j=1;j<=m;j++){
        for(ll i=1;i<=n;i++){
            if(v[i][j]=='X') bou[i][j][2]=i;
            else bou[i][j][2]=bou[i-1][j][2];
        }
        for(ll i=n;i>=1;i--){
            if(v[i][j]=='X') bou[i][j][3]=i;
            else bou[i][j][3]=bou[i+1][j][3];
        }
    }
    dfs(st.ff,st.ss,bou);
    if(vis[x1][y2]) cout<<"YES\n";
    else cout<<"NO\n";
}

int main(){
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll t=1;
    // cin>>t;
    for(ll _=1;_<=t;_++){
        // cout<<"Scenario #"<<_<<":\n";
        solve();
    }
}
#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...