Submission #1189246

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189246		Zakir060	Robots (APIO13_robots)	C++20	30 / 100	1596 ms	40188 KiB

robots

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <tuple> // For pairs or tuples if needed

using namespace std;

// Maximum dimensions and robot count based on constraints (n <= 9)
const int MAX_N = 9;
const int MAX_W = 50; // Assuming reasonable max dimensions
const int MAX_H = 50;

int N, W, H;
vector<string> grid;

// --- Robot Representation ---
struct Robot {
    int min_label;
    int max_label;
    int r, c;

    // Needed for sorting and using in maps/sets
    bool operator<(const Robot& other) const {
        if (min_label != other.min_label) return min_label < other.min_label;
        if (max_label != other.max_label) return max_label < other.max_label;
        if (r != other.r) return r < other.r;
        return c < other.c;
    }

     // Needed for comparison in maps/sets
    bool operator==(const Robot& other) const {
        return min_label == other.min_label &&
               max_label == other.max_label &&
               r == other.r &&
               c == other.c;
    }
};

// --- State Representation ---
// A state is defined by the set of robots currently existing.
// We use a vector sorted by min_label for canonical representation.
using State = vector<Robot>;

// --- Helper Functions ---

// Check if coordinates are within the grid boundaries
bool is_valid(int r, int c) {
    return r >= 0 && r < H && c >= 0 && c < W;
}

// Get the character at a grid cell (handling boundary checks)
char get_grid_char(int r, int c) {
    if (!is_valid(r, c)) {
        return 'x'; // Treat outside as an obstacle/wall
    }
    return grid[r][c];
}

// --- Movement Simulation ---

// Directions: 0: Up (-1, 0), 1: Right (0, +1), 2: Down (+1, 0), 3: Left (0, -1)
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

// Function to calculate the final position after a push
pair<int, int> simulate_move(int start_r, int start_c, int push_dir) {
    int r = start_r;
    int c = start_c;
    int current_dir = push_dir; // Initial direction robot *intends* to move

    // --- Rotation if starting on a plate ---
    char start_plate = get_grid_char(r, c);
    if (start_plate == 'A') { // Anti-clockwise
        // Push Up(0) -> Left(3)
        // Push Right(1) -> Up(0)
        // Push Down(2) -> Right(1)
        // Push Left(3) -> Down(2)
        current_dir = (push_dir + 3) % 4;
    } else if (start_plate == 'C') { // Clockwise
        // Push Up(0) -> Right(1)
        // Push Right(1) -> Down(2)
        // Push Down(2) -> Left(3)
        // Push Left(3) -> Up(0)
        current_dir = (push_dir + 1) % 4;
    }
    // If not on a plate, current_dir remains push_dir

    // --- Simulate movement step-by-step ---
    while (true) {
        int next_r = r + dr[current_dir];
        int next_c = c + dc[current_dir];
        char next_cell = get_grid_char(next_r, next_c);

        // Check for collision (wall or occlusion)
        if (next_cell == 'x' || !is_valid(next_r, next_c)) {
            break; // Stop at the current position (r, c)
        }

        // Move to the next cell
        r = next_r;
        c = next_c;

        // --- Rotation if landing on a plate ---
        if (next_cell == 'A') { // Anti-clockwise rotation of direction
             // Moving Up(0) -> new dir Left(3)
             // Moving Right(1) -> new dir Up(0)
             // Moving Down(2) -> new dir Right(1)
             // Moving Left(3) -> new dir Down(2)
            current_dir = (current_dir + 3) % 4;
        } else if (next_cell == 'C') { // Clockwise rotation of direction
             // Moving Up(0) -> new dir Right(1)
             // Moving Right(1) -> new dir Down(2)
             // Moving Down(2) -> new dir Left(3)
             // Moving Left(3) -> new dir Up(0)
            current_dir = (current_dir + 1) % 4;
        }
        // If it's '.', numeric, or the initial location, direction doesn't change here
    }

    return {r, c}; // Return the final position
}

// --- Merging Logic ---

// Function to perform all possible merges at a given location
State merge_robots_at_location(const State& robots_at_loc) {
    if (robots_at_loc.size() <= 1) {
        return robots_at_loc; // No merging possible
    }

    State current_robots = robots_at_loc;
    bool merged;

    do {
        merged = false;
        State next_robots;
        vector<bool> used(current_robots.size(), false);

        // Sort to easily find adjacent ranges (optional but can help)
        // sort(current_robots.begin(), current_robots.end()); // Already sorted by state canonicalization

        for (int i = 0; i < current_robots.size(); ++i) {
            if (used[i]) continue;

            bool found_merge = false;
            for (int j = i + 1; j < current_robots.size(); ++j) {
                if (used[j]) continue;

                // Check for compatibility (consecutive labels)
                Robot r1 = current_robots[i];
                Robot r2 = current_robots[j];

                // Ensure they are at the same location (should be guaranteed by input)
                if (r1.r != r2.r || r1.c != r2.c) continue;

                if (r1.max_label + 1 == r2.min_label) {
                    // Merge r1 and r2
                    Robot merged_robot = {r1.min_label, r2.max_label, r1.r, r1.c};
                    next_robots.push_back(merged_robot);
                    used[i] = true;
                    used[j] = true;
                    merged = true;
                    found_merge = true;
                    break; // Merge r1 with the first compatible r2 found
                } else if (r2.max_label + 1 == r1.min_label) {
                    // Merge r2 and r1
                     Robot merged_robot = {r2.min_label, r1.max_label, r1.r, r1.c};
                    next_robots.push_back(merged_robot);
                    used[i] = true;
                    used[j] = true;
                    merged = true;
                    found_merge = true;
                    break; // Merge r1 with the first compatible r2 found
                }
            }
             // If robot i didn't merge with any other robot
            if (!found_merge) {
                // Only add if it wasn't marked used by merging with a previous robot
                if(!used[i]) {
                   next_robots.push_back(current_robots[i]);
                   used[i] = true; // Mark as processed for this pass
                }
            }
        }
         // Update the list of robots for the next merging iteration
        current_robots = next_robots;
        sort(current_robots.begin(), current_robots.end()); // Keep sorted for consistency


    } while (merged); // Repeat until no more merges occur in a pass

    return current_robots;
}

// Canonicalize state by sorting robots
State canonicalize(State s) {
    sort(s.begin(), s.end());
    return s;
}

// --- Breadth-First Search (BFS) ---
int solve() {
    // 1. Find initial state
    State initial_state;
    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (isdigit(grid[r][c])) {
                int label = grid[r][c] - '0';
                initial_state.push_back({label, label, r, c});
            }
        }
    }
    initial_state = canonicalize(initial_state); // Canonicalize initial state

    // 2. Initialize BFS
    queue<State> q;
    map<State, int> dist; // Map state to minimum pushes

    q.push(initial_state);
    dist[initial_state] = 0;

    // 3. BFS loop
    while (!q.empty()) {
        State current_state = q.front();
        q.pop();

        int current_dist = dist[current_state];

        // Check for goal state
        if (current_state.size() == 1 && current_state[0].min_label == 1 && current_state[0].max_label == N) {
            return current_dist; // Found the solution
        }

        // Explore possible moves (pushing each robot in 4 directions)
        for (int i = 0; i < current_state.size(); ++i) { // Iterate through robots in current state
            Robot robot_to_move = current_state[i];

            for (int push_dir = 0; push_dir < 4; ++push_dir) { // Iterate through push directions
                // Simulate the move
                pair<int, int> final_pos = simulate_move(robot_to_move.r, robot_to_move.c, push_dir);
                int final_r = final_pos.first;
                int final_c = final_pos.second;

                // Create the potential next state (before merging)
                State next_state_unmerged = current_state;
                next_state_unmerged[i].r = final_r;
                next_state_unmerged[i].c = final_c;

                // Group robots by location for merging
                map<pair<int, int>, State> robots_by_location;
                for(const auto& robot : next_state_unmerged) {
                    robots_by_location[{robot.r, robot.c}].push_back(robot);
                }

                // Perform merging at each location where merges might occur
                State next_state_merged;
                for(auto const& [pos, robots_at_pos] : robots_by_location) {
                    State merged_robots = merge_robots_at_location(robots_at_pos);
                    // Add the results of merging back to the overall state
                    next_state_merged.insert(next_state_merged.end(), merged_robots.begin(), merged_robots.end());
                }


                // Canonicalize the final state after merging
                State final_next_state = canonicalize(next_state_merged);

                // Check if this state has been visited
                if (dist.find(final_next_state) == dist.end()) {
                    dist[final_next_state] = current_dist + 1;
                    q.push(final_next_state);
                }
                // If visited but found a shorter path (shouldn't happen in BFS, but good practice)
                // else if (current_dist + 1 < dist[final_next_state]) {
                //    dist[final_next_state] = current_dist + 1;
                //    q.push(final_next_state); // Re-add with shorter distance (though BFS naturally finds shortest)
                // }
            }
        }
    }

    // If the queue becomes empty and goal not reached
    return -1;
}

// --- Main Function ---
int main() {
    // Optimize C++ I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input
    cin >> N >> W >> H;
    grid.resize(H);
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }

    // Solve the problem
    int result = solve();

    // Print output
    cout << result << endl;

    return 0;
}

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