Submission #1230536

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230536		just	Toy (CEOI24_toy)	C++20	14 / 100	1597 ms	90584 KiB

Main

#include "bits/stdc++.h"
using namespace std;
 
#define vec vector
#define int long long
#define all(x) (x).begin(), (x).end()
 
const int mod = 1e9 + 7;
const int inf = LLONG_MAX;
 
using pii = pair<int, int>;

using Point = pii;
#define X first
#define Y second


int n, m, w, h;
bool grid[100][100];
Point start;


bool valid(Point p) {
    return p.X >= 0 && p.X < n && p.Y >= 0 && p.Y < m && !grid[p.X][p.Y];
}

Point meeting_point(Point H, Point V) {
    return {H.X, V.Y};
}

bool valid(Point H, Point V) {
    if (!valid(H) || !valid(V)) return false;
    if (V.Y - H.Y > w - 1 || H.X - V.X > h - 1 || V.Y < H.Y || H.X < V.X) return false;
    
    for (int i = 0; i < w; i++) {
        if (!valid({H.X, H.Y + i})) return false;
    }

    for (int i = 0; i < h; i++) {
        if (!valid({V.X + i, V.Y})) return false;
    }

    return true;
}

char print_buf[100][100];
void print(Point H, Point V) {
    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) print_buf[i][j] = grid[i][j] ? '-' : '.';

    print_buf[start.X][start.Y] = '*';
    for (int i = 0; i < w; i++) print_buf[H.X][H.Y + i] = 'H';
    for (int i = 0; i < h; i++) print_buf[V.X + i][V.Y] = 'V';

    Point M = meeting_point(H, V);
    print_buf[M.X][M.Y] = 'M';

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) cout << print_buf[i][j];
        cout << '\n';
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> m >> n >> w >> h;
    
    Point H, V;
    {
        int x, y; 
        
        cin >> x >> y;
        H = {y, x};
        cin >> x >> y;
        V = {y, x};
    }


    for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) {
        char c; cin >> c;
        grid[i][j] = c == 'X';
        if (c == '*') start = {i, j};
    }

    // print(H, V);

    assert(valid(H) && valid(V));

    auto M = meeting_point(H, V);
    if (M == start) {
        cout << "YES\n";
        return 0;
    }

    // calculate the distance from the starting point to every square
    // to use as a heuristic
    vec<vec<int>> dist(n, vec<int>(m, inf));

    const int dx[] = {0, 1, 0, -1};
    const int dy[] = {1, 0, -1, 0};

    {
        queue<Point> q;
        q.push(start);
        dist[start.X][start.Y] = 0;

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

            for (int i = 0; i < 4; i++) {
                Point n = {x + dx[i], y + dy[i]};
                if (valid(n) && dist[n.X][n.Y] > dist[x][y] + 1) {
                    dist[n.X][n.Y] = dist[x][y] + 1;
                    q.push(n);
                }
            }
        }
    }

    using State = pair<Point, Point>;
    priority_queue<pair<int, State>> q;
    set<State> vis;

    q.push({0, {H, V}});
    vis.insert({H, V});

    while (!q.empty()) {
        auto [_, state] = q.top();
        q.pop();
        auto [H, V] = state;

        for (int s: {1, -1}) {
            for (int i = 0; i < 4; i++) {
                Point nH = {H.X + (i == 0) * s, H.Y + (i == 1) * s};
                Point nV = {V.X + (i == 2) * s, V.Y + (i == 3) * s};

                if (valid(nH, nV)) {
                    
                    auto M = meeting_point(nH, nV);
                    if (M == start) {
                        cout << "YES\n"; 
                        return 0;
                    }

                    if (vis.count({nH, nV})) continue;

                    q.push({-dist[M.X][M.Y], {nH, nV}});
                    vis.insert({nH, nV});
                }
            }
        }
    }

    cout << "NO\n";

    

}

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