Submission #1168180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1168180		juliany2	Toy (CEOI24_toy)	C++20	100 / 100	77 ms	38552 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define all(x) (x).begin(), (x).end()


int main() {
    cin.tie(0)->sync_with_stdio(false);

    int n, m, w, h;
    cin >> n >> m >> w >> h;

    swap(n, m);

    int x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    swap(x1, y1);
    swap(x2, y2);

    vector<string> g(n);
    for (string &i : g)
        cin >> i;

    vector<vector<int>> l(n, vector<int> (m, -1));
    vector<vector<int>> r(n, vector<int> (m, m));
    vector<vector<int>> u(n, vector<int> (m, -1));
    vector<vector<int>> d(n, vector<int> (m, n));

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (g[i][j] == 'X') {
                l[i][j] = j;
                u[i][j] = i;
                continue;
            }

            if (i > 0)
                u[i][j] = u[i - 1][j];
            if (j > 0)
                l[i][j] = l[i][j - 1];
        }
    }

    for (int i = n - 1; i >= 0; i--) {
        for (int j = m - 1; j >= 0; j--) {
            if (g[i][j] == 'X') {
                r[i][j] = j;
                d[i][j] = i;
                continue;
            }

            if (i < n - 1)
                d[i][j] = d[i + 1][j];
            if (j < m - 1)
                r[i][j] = r[i][j + 1];
        }
    }

    queue<array<int, 2>> q;
    vector<vector<bool>> vis(n, vector<bool> (m));

    vis[x1][y2] = 1;
    q.push({x1, y2});

    while (q.size()) {
        auto [x, y] = q.front();
        q.pop();

        if (g[x][y] == '*') {
            cout << "YES" << '\n';
            return 0;
        }

        // right
        if (y + 1 < m && g[x][y + 1] != 'X' && !vis[x][y + 1]) {
            if (min(d[x][y], d[x][y + 1]) - max(u[x][y], u[x][y + 1]) - 1 >= h) {
                vis[x][y + 1] = 1;
                q.push({x, y + 1});
            }
        }

        // left
        if (y - 1 >= 0 && g[x][y - 1] != 'X' && !vis[x][y - 1]) {
            if (min(d[x][y], d[x][y - 1]) - max(u[x][y], u[x][y - 1]) - 1 >= h) {
                vis[x][y - 1] = 1;
                q.push({x, y - 1});
            }
        }

        // down
        if (x + 1 < n && g[x + 1][y] != 'X' && !vis[x + 1][y]) {
            if (min(r[x][y], r[x + 1][y]) - max(l[x][y], l[x + 1][y]) - 1 >= w) {
                vis[x + 1][y] = 1;
                q.push({x + 1, y});
            }
        }

        // up
        if (x - 1 >= 0 && g[x - 1][y] != 'X' && !vis[x - 1][y]) {
            if (min(r[x][y], r[x - 1][y]) - max(l[x][y], l[x - 1][y]) - 1 >= w) {
                vis[x - 1][y] = 1;
                q.push({x - 1, y});
            }
        }
    }

    cout << "NO" << '\n';

    return 0;
}

• Subtask 0: 0 / 0
• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 9 / 9
• Subtask 4: 29 / 29
• Subtask 5: 27 / 27