제출 #1342724

#제출 시각아이디문제언어결과실행 시간메모리
1342724vjudge1Toy (CEOI24_toy)C++20
100 / 100
932 ms713936 KiB
#include <bits/stdc++.h>
using namespace std;
#define ld long double
#define ll long long
#define MAX 5001
ll w, h, k, l;
vector<vector<ll>> blw, blh; 
vector<ll> getw(ll x, ll y){
    if (x >= h || y >= w || x < 0 || y < 0) return {0, 0};
    auto it = upper_bound(blw[x].begin(), blw[x].end(), y);
    ll ri = *it - 1;
    it--;
    ll le = *it + 1;
    return {le, ri};
}
vector<ll> geth(ll x, ll y){
    if (x >= h || y >= w || x < 0 || y < 0) return {0, 0};
    auto it = upper_bound(blh[y].begin(), blh[y].end(), x);
    ll ri = *it - 1;
    it--;
    ll le = *it + 1;
    return {le, ri};
}
vector<vector<int>> vis;
ll fov(vector<ll> fi, vector<ll> se){
    return max(0LL, min(fi[1], se[1]) - max(fi[0], se[0]) + 1);
}
void dfs(int x, int y){
    if (vis[x][y] == 1) return;
    vis[x][y] = 1;
    vector<ll> wi = getw(x, y), he = geth(x, y);
    if (fov(wi, getw(x + 1, y)) >= k && he[0] <= x + 1 && x + 1 <= he[1]){
        dfs(x + 1, y);
    }
    if (fov(wi, getw(x - 1, y)) >= k && he[0] <= x - 1 && x - 1 <= he[1]){
        dfs(x - 1, y);
    }
    if (fov(he, geth(x, y + 1)) >= l && wi[0] <= y + 1 && y + 1 <= wi[1]){
        dfs(x, y + 1);
    }
    if (fov(he, geth(x, y - 1)) >= l && wi[0] <= y - 1 && y - 1 <= wi[1]){
        dfs(x, y - 1);
    }
}
int main(){
    cin>>w>>h>>k>>l;
    ll x1, y1, x2, y2, dx, dy;
    cin>>x1>>y1>>x2>>y2;
    blw.assign(h, vector<ll>()), blh.assign(w, vector<ll>());
    for (int i = 0; i < w; i++) blh[i].push_back(-1);
    for (int i = 0; i < h; i++){
        blw[i].push_back(-1);
        string s;
        cin>>s;
        for (int j = 0; j < w; j++){
            if (s[j] == 'X') blw[i].push_back(j), blh[j].push_back(i);
            if (s[j] == '*') dx = i, dy = j;
        }
        blw[i].push_back(w);
    }
    for (int i = 0; i < w; i++) blh[i].push_back(h);
    vis.assign(h, vector<int>(w, 0));
    dfs(y1, x2);
    if (vis[dx][dy] == 1) cout<<"YES\n";
    else cout<<"NO\n";
}
#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...