Submission #1164003

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164003		ch3zburger	Walk (CEOI06_walk)	C++20	0 / 100	952 ms	196608 KiB

walk

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tiii; // (x, y, dir)

const int INF = 1e9;
const int dx[4] = {1, -1, 0, 0}; // right, left, up, down
const int dy[4] = {0, 0, 1, -1};
const int dir_type[4] = {1, 1, 2, 2}; // 1=horizontal, 2=vertical

int main() {
    int X, Y, N;
    cin >> X >> Y >> N;
    
    // Mark blocked squares
    set<pii> blocked;
    for (int i = 0; i < N; i++) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        int xmin = min(x1, x2), xmax = max(x1, x2);
        int ymin = min(y1, y2), ymax = max(y1, y2);
        for (int x = xmin; x <= xmax; x++)
            for (int y = ymin; y <= ymax; y++)
                blocked.insert({x, y});
    }
    
    // BFS
    vector<vector<vector<int>>> dist(2001, vector<vector<int>>(2001, vector<int>(3, INF))); // Adjust size as needed
    vector<vector<vector<tiii>>> parent(2001, vector<vector<tiii>>(2001, vector<tiii>(3)));
    queue<tiii> q;
    
    dist[0][0][0] = 0;
    q.push({0, 0, 0});
    
    while (!q.empty()) {
        auto [x, y, dir] = q.front();
        q.pop();
        
        for (int d = 0; d < 4; d++) {
            int nx = x + dx[d], ny = y + dy[d];
            int new_dir = dir_type[d];
            
            // Skip if out of bounds, blocked, or same direction as previous
            if (nx < -1000 || nx > 2000 || ny < -1000 || ny > 2000 || blocked.count({nx, ny})) continue;
            if (dir != 0 && dir == new_dir) continue;
            
            if (dist[nx][ny][new_dir] == INF) {
                dist[nx][ny][new_dir] = dist[x][y][dir] + 1;
                parent[nx][ny][new_dir] = {x, y, dir};
                q.push({nx, ny, new_dir});
            }
        }
    }
    
    // Find shortest path to (X, Y)
    int L = INF, final_dir = -1;
    for (int d = 1; d <= 2; d++) {
        if (dist[X][Y][d] < L) {
            L = dist[X][Y][d];
            final_dir = d;
        }
    }
    
    if (L == INF) {
        cout << "No path found\n"; // Shouldn’t happen given problem constraints
        return 0;
    }
    
    // Reconstruct path
    vector<pair<int, int>> segments;
    int cx = X, cy = Y, cd = final_dir;
    while (!(cx == 0 && cy == 0 && cd == 0)) {
        auto [px, py, pd] = parent[cx][cy][cd];
        int dx = cx - px, dy = cy - py;
        segments.push_back({dx, dy});
        cx = px; cy = py; cd = pd;
    }
    
    // Merge consecutive moves into segments
    vector<pair<int, int>> final_segments;
    int curr_dx = 0, curr_dy = 0;
    for (int i = segments.size() - 1; i >= 0; i--) {
        int dx = segments[i].first, dy = segments[i].second;
        if (dx != 0) {
            if (curr_dy != 0) {
                final_segments.push_back({0, curr_dy});
                curr_dy = 0;
            }
            curr_dx += dx;
        } else {
            if (curr_dx != 0) {
                final_segments.push_back({curr_dx, 0});
                curr_dx = 0;
            }
            curr_dy += dy;
        }
    }
    if (curr_dx != 0) final_segments.push_back({curr_dx, 0});
    if (curr_dy != 0) final_segments.push_back({0, curr_dy});
    
    // Output
    cout << L << "\n";
    cout << final_segments.size() << "\n";
    for (auto [dx, dy] : final_segments) {
        cout << dx << " " << dy << "\n";
    }
    
    return 0;
}

• Subtask 1: 0 / 100