Submission #1125426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125426		ALTAKEXE	Robots (APIO13_robots)	C++17	0 / 100	160 ms	229376 KiB

robots

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9; // A large value representing "infinity"
const int MAX_N = 9; // Maximum number of robots
const int MAX_V = 500 * 500; // Maximum number of reachable grids (500x500 room)

// Grid dimensions
int w, h, n;
vector<string> grid;
vector<pair<int, int>> robot_positions; // Initial positions of robots

// Distance matrix
vector<vector<int>> dist(MAX_V, vector<int>(MAX_V, INF)); // All-pairs shortest path distances

// Convert 2D coordinates to a single integer ID
inline int get_id(int x, int y) {
    return x * w + y;
}

// Precompute all-pairs shortest path distances using BFS
void compute_distances() {
    int dx[] = {-1, 1, 0, 0}; // Directions for movement
    int dy[] = {0, 0, -1, 1};
    
    for (int x = 0; x < h; ++x) {
        for (int y = 0; y < w; ++y) {
            if (grid[x][y] == 'x') continue; // Skip occluded cells
            
            int start = get_id(x, y);
            queue<pair<int, int>> q;
            q.push({x, y});
            dist[start][start] = 0;

            while (!q.empty()) {
                auto [cx, cy] = q.front();
                q.pop();
                int curr_id = get_id(cx, cy);

                for (int d = 0; d < 4; ++d) {
                    int nx = cx, ny = cy;
                    int pushes = 0;

                    // Simulate movement in a straight line
                    while (true) {
                        int tx = nx + dx[d], ty = ny + dy[d];
                        if (tx < 0 || tx >= h || ty < 0 || ty >= w || grid[tx][ty] == 'x') break;
                        nx = tx;
                        ny = ty;

                        // Rotate if on a rotating plate
                        if (grid[nx][ny] == 'A') { // Counter-clockwise
                            tie(dx[d], dy[d]) = make_pair(-dy[d], dx[d]);
                        } else if (grid[nx][ny] == 'C') { // Clockwise
                            tie(dx[d], dy[d]) = make_pair(dy[d], -dx[d]);
                        }
                        pushes++;
                    }

                    int next_id = get_id(nx, ny);
                    if (dist[start][next_id] > pushes) {
                        dist[start][next_id] = pushes;
                        q.push({nx, ny});
                    }
                }
            }
        }
    }
}

// Solve the DP problem for merging robots
int solve() {
    // Base case: cost to move a single robot
    vector<vector<vector<int>>> dp(MAX_N, vector<vector<int>>(MAX_N, vector<int>(MAX_V, INF)));
    for (int i = 0; i < n; ++i) {
        int pos = get_id(robot_positions[i].first, robot_positions[i].second);
        dp[i][i][pos] = 0; // No cost to keep a robot at its initial position
    }

    // Compute merging costs
    for (int length = 1; length < n; ++length) { // Range size
        for (int i = 0; i + length < n; ++i) {   // Start of the range
            int j = i + length; // End of the range

            for (int u = 0; u < h * w; ++u) {
                if (dist[u][u] == INF) continue; // Skip unreachable cells
                for (int k = i; k < j; ++k) {
                    dp[i][j][u] = min(dp[i][j][u], dp[i][k][u] + dp[k + 1][j][u]);
                }
                for (int v = 0; v < h * w; ++v) {
                    dp[i][j][u] = min(dp[i][j][u], dp[i][j][v] + dist[v][u]);
                }
            }
        }
    }

    // Get the minimum cost to merge all robots
    int result = INF;
    for (int u = 0; u < h * w; ++u) {
        result = min(result, dp[0][n - 1][u]);
    }
    return result == INF ? -1 : result;
}

int main() {
    cin >> n >> w >> h;
    grid.resize(h);
    for (int i = 0; i < h; ++i) {
        cin >> grid[i];
    }

    // Parse initial robot positions
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (isdigit(grid[i][j])) {
                robot_positions.push_back({i, j});
            }
        }
    }

    compute_distances();
    cout << solve() << endl;

    return 0;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 40