Submission #1125427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125427		ALTAKEXE	Robots (APIO13_robots)	C++17	Compilation error	0 ms	0 KiB

robots

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

const int INF = 1e9; // Infinity
const int MAX_N = 9; // Maximum number of robots
const int MAX_V = 500 * 500; // Maximum number of reachable grids

int w, h, n; // Width, height, and number of robots
vector<string> grid;
vector<pair<int, int>> robot_positions;
vector<int> reachable_cells; // List of reachable grid IDs
unordered_map<int, int> cell_to_index; // Map grid ID to compressed index
vector<vector<int>> dist; // Distances between reachable cells

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

// Precompute reachable cells and distances
void preprocess() {
    int dx[] = {-1, 1, 0, 0};
    int dy[] = {0, 0, -1, 1};

    queue<pair<int, int>> q;
    vector<vector<bool>> visited(h, vector<bool>(w, false));

    // Start BFS from all robot positions
    for (auto [x, y] : robot_positions) {
        q.push({x, y});
        visited[x][y] = true;
    }

    // BFS for reachable cells
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        int cell_id = get_id(cx, cy);
        reachable_cells.push_back(cell_id);
        cell_to_index[cell_id] = (int)reachable_cells.size() - 1;

        for (int d = 0; d < 4; ++d) {
            int nx = cx, ny = cy;
            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 plate
                if (grid[nx][ny] == 'A') {
                    tie(dx[d], dy[d]) = make_pair(-dy[d], dx[d]);
                } else if (grid[nx][ny] == 'C') {
                    tie(dx[d], dy[d]) = make_pair(dy[d], -dx[d]);
                }
            }
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }

    // Compute pairwise distances between reachable cells
    int V = reachable_cells.size();
    dist.assign(V, vector<int>(V, INF));
    for (int i = 0; i < V; ++i) {
        queue<int> q;
        vector<int> d(V, INF);
        d[i] = 0;
        q.push(i);

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            int x = reachable_cells[u] / w, y = reachable_cells[u] % w;

            for (int d = 0; d < 4; ++d) {
                int nx = x, ny = y;
                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;
                }
                int v = cell_to_index[get_id(nx, ny)];
                if (d[v] > d[u] + 1) {
                    d[v] = d[u] + 1;
                    q.push(v);
                }
            }
        }

        // Store distances
        for (int j = 0; j < V; ++j) {
            dist[i][j] = d[j];
        }
    }
}

// Solve using DP with bitmask
int solve() {
    int V = reachable_cells.size();
    vector<vector<int>> dp(1 << n, vector<int>(V, INF));

    // Initialize DP for single robots
    for (int i = 0; i < n; ++i) {
        int start = cell_to_index[get_id(robot_positions[i].first, robot_positions[i].second)];
        dp[1 << i][start] = 0;
    }

    // Iterate over all subsets of robots
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int u = 0; u < V; ++u) {
            if (dp[mask][u] == INF) continue;

            // Try merging with other subsets
            for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
                int rest = mask ^ submask;

                for (int v = 0; v < V; ++v) {
                    dp[mask][v] = min(dp[mask][v], dp[submask][u] + dp[rest][v] + dist[u][v]);
                }
            }
        }
    }

    // Find the minimum cost to merge all robots
    int result = INF;
    for (int u = 0; u < V; ++u) {
        result = min(result, dp[(1 << 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 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});
            }
        }
    }

    preprocess();
    cout << solve() << endl;

    return 0;
}

Compilation message (stderr)

robots.cpp: In function 'void preprocess()':
robots.cpp:87:22: error: invalid types 'int[int]' for array subscript
   87 |                 if (d[v] > d[u] + 1) {
      |                      ^
robots.cpp:87:29: error: invalid types 'int[int]' for array subscript
   87 |                 if (d[v] > d[u] + 1) {
      |                             ^
robots.cpp:88:22: error: invalid types 'int[int]' for array subscript
   88 |                     d[v] = d[u] + 1;
      |                      ^
robots.cpp:88:29: error: invalid types 'int[int]' for array subscript
   88 |                     d[v] = d[u] + 1;
      |                             ^