Submission #1361565

#TimeUsernameProblemLanguageResultExecution timeMemory
1361565mahmudisaliToy (CEOI24_toy)C++20
0 / 100
0 ms344 KiB
// Mahmud Isali
#pragma oprimize ("O3")

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
// using namespace __gnu_pbds;

#define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define F first
#define S second
//  #define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

const long long INF = 1e18, MOD = 1e9 + 7, N = 1500 + 10;
int W,H,K,L,xh,yh,xv,yv;
bool used[N][N];
char v[N][N];
int up[N][N], dw[N][N], lf[N][N], rg[N][N];
void dfs(int x, int y) {
    if(x < 1 || x > H || y < 1 || y > W || used[x][y]) return;
    if(rg[x][y] - lf[x][y] + 1 < K) return;
    if(dw[x][y] - up[x][y] + 1 < L) return;
    used[x][y] = true;
    if(x > 1) {
        int Lf = max(lf[x][y], lf[x-1][y]);
        int Rg = min(rg[x][y], rg[x-1][y]);
        if(Rg - Lf + 1 >= K)
            dfs(x-1, y);
    }

    if(x < H) {
        int Lf = max(lf[x][y], lf[x+1][y]);
        int Rg = min(rg[x][y], rg[x+1][y]);
        if(Rg - Lf + 1 >= K)
            dfs(x+1, y);
    }
    if(y > 1) {
        int Up = max(up[x][y], up[x][y-1]);
        int Dw = min(dw[x][y], dw[x][y-1]);
        if(Dw - Up + 1 >= L)
            dfs(x, y-1);
    }

    if(y < W) {
        int Up = max(up[x][y], up[x][y+1]);
        int Dw = min(dw[x][y], dw[x][y+1]);
        if(Dw - Up + 1 >= L)
            dfs(x, y+1);
    }
}
void prep() {
    for(int i = 1; i <= H; i++) {
        int lft = 0, rgh = W + 1;
        for(int j = 1; j <= W; j++) {
            if(v[i][j] == 'X')  lft = j;
            lf[i][j] = lft;
        }
        for(int j = W; j >= 1; j--) {
            if(v[i][j] == 'X')  rgh = j;
            rg[i][j] = rgh;
        }
    }
    for(int i = 1; i <= W; i++) {
        int upp = 0, dwn = H + 1;
        for(int j = 1; j <= H; j++) {
            if(v[j][i] == 'X')  upp = j;
            up[j][i] = upp;
        }
        for(int j = H; j >= 1; j--) {
            if(v[j][i] == 'X')  dwn = j;
            dw[j][i] = dwn;
        }
    }
}
void solve() {
    cin >> W >> H >> K >> L >> xh >> yh >> xv >> yv;
    xh++,yh++,xv++,yv++;
    int sx = 0, sy = 0;
    for(int i = 1; i <= H; i++) {
        for(int j = 1; j <= W; j++) {
            cin >> v[i][j];
            if(v[i][j] == '*')  sx = i, sy = j;
        }
    }
    prep();
    dfs(yh, xv);
    cout << (used[sx][sy] ? "YES" : "NO");
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int t = 1;
    // cin >> t;
    for(int T = 1; T <= t; T++) {
        // cout << "Case: " << T << endl;
        solve();
    }
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...