Submission #1342823

#TimeUsernameProblemLanguageResultExecution timeMemory
1342823vjudge1Toy (CEOI24_toy)C++20
100 / 100
186 ms75728 KiB
#include <bits/stdc++.h>
    #define debug(...)
#define GOOD_LUCK ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define int long long
#define endl "\n"
#define ff first
#define ss second
#define pb push_back
#define all(v) v.begin(), v.end()
using namespace std;

int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
constexpr int MAX = 2e+5 + 1, INF = 2e+10, MOD = 1e+9 + 7, K = 31;
int n, m, x, y;
vector <vector <char>> g, col;
vector <vector <int>> vu, vd, vl, vr;

bool is(int a, int b) {
    if (a <= n && b <= m && a > 0 && b > 0) return 1;
    return 0;
}

void bfs(int sa, int sb) {
    queue <pair<int, int>> q;
    q.push({sa, sb});
    col[sa][sb] = 1;
    while (!q.empty()) {
        auto u = q.front();
        q.pop();
        int ua = u.ff, ub = u.ss;
        for (int i = 0; i < 2; i++) {
            int a = ua + dx[i], b = ub + dy[i];
            if (!is(a, b)) continue;
            if (g[a][b] == 'X') continue;
            if (col[a][b]) continue;
            int l = min(vl[a][b], vl[ua][ub]), r = min(vr[a][b], vr[ua][ub]);
            if (r + l - 1 < y) continue;
            q.push({a, b});
            col[a][b] = 1;
        }
        for (int i = 2; i < 4; i++) {
            int a = ua + dx[i], b = ub + dy[i];
            if (!is(a, b)) continue;
            if (g[a][b] == 'X') continue;
            if (col[a][b]) continue;
            int l = min(vu[a][b], vu[ua][ub]), r = min(vd[a][b], vd[ua][ub]);
            if (r + l - 1 < x) continue;
            q.push({a, b});
            col[a][b] = 1;
        }
    }
}

void _() {
    cin >> n >> m >> x >> y;
    swap(n, m);
    swap(x, y);
    int a, b, t1, t2;
    cin >> t1 >> b >> a >> t2;
    ++a, ++b;
    swap(a, b);
    g.assign(n+1, vector <char>(m+1));
    col.assign(n+1, vector <char>(m+1, 0));
    vu.assign(n+1, vector <int>(m+1, 1));
    vl.assign(n+1, vector <int>(m+1, 1));
    vr.assign(n+1, vector <int>(m+1, 1));
    vd.assign(n+1, vector <int>(m+1, 1));
    int ta, tb;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> g[i][j];
            if (g[i][j] == 'X') {
                vu[i][j] = vl[i][j] = vr[i][j] = vd[i][j] = -INF;
            }
            if (g[i][j] == '*') ta = i, tb = j;
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= m; j++) {
            if (g[i][j] == 'X') continue;
            vl[i][j] = max(vl[i][j], vl[i][j-1] + 1);
        }
        for (int j = m - 1; j >= 1; j--) {
            if (g[i][j] == 'X') continue;
            vr[i][j] = max(vr[i][j], vr[i][j+1] + 1);
        }
    }
    for (int j = 1; j <= m; j++) {
        for (int i = 2; i <= n; i++) {
            if (g[i][j] == 'X') continue;
            vu[i][j] = max(vu[i][j], vu[i-1][j] + 1);
        }
        for (int i = n - 1; i >= 1; i--) {
            if (g[i][j] == 'X') continue;
            vd[i][j] = max(vd[i][j], vd[i+1][j] + 1);
        }
    }
    bfs(a, b);
    if (col[ta][tb]) {
        cout << "YES";
    }
    else cout << "NO";
}

signed main() {

    GOOD_LUCK

    int tests=1;
    // cin >> tests;
    for (int i=1; i <= tests; i++) {
        _();
        cout << endl;
    }

    return 0;
}
#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...