Submission #1188230

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188230		ainunnajib	Robots (APIO13_robots)	C++20	30 / 100	1596 ms	72948 KiB

robots

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <tuple>   // For std::tie used in comparison
#include <vector>
#include <algorithm> // For std::sort
#include <cctype>    // For std::isdigit

using namespace std;

// Struct to represent a robot (original or composite)
struct Robot {
    int min_l, max_l; // Min and max labels of merged robots
    int r, c;         // Row and column position

    // Comparison operator for sorting and using in std::set/map.
    // Sort primarily by labels, then by position for a consistent canonical form.
    bool operator<(const Robot& other) const {
        return tie(min_l, max_l, r, c) < tie(other.min_l, other.max_l, other.r, other.c);
    }
     // Equality operator (needed for some container operations, though < is primary for set)
    bool operator==(const Robot& other) const {
        return tie(min_l, max_l, r, c) == tie(other.min_l, other.max_l, other.r, other.c);
    }
};

// Global variables for grid dimensions and content
int N; // Number of initial robots
int W; // Grid width
int H; // Grid height
vector<string> grid; // Grid layout ('x', '.', 'A', 'C')
vector<pair<int, int>> initial_pos; // Store initial positions for robots 1 to N

// 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 check if a cell is valid (within bounds and not an obstacle)
bool isValid(int r, int c) {
    return r >= 0 && r < H && c >= 0 && c < W && grid[r][c] != 'x';
}

// Function to simulate robot movement from (r, c) in direction 'dir'.
// 'dir' is passed by reference as it can change due to rotation plates.
// Returns the final position {final_r, final_c}.
pair<int, int> simulate_move(int r, int c, int& dir) {
    // 1. Handle initial rotation if starting on a plate when pushed
    if (grid[r][c] == 'A') { // Anti-clockwise: Up->Left(3), Right->Up(0), Down->Right(1), Left->Down(2)
        dir = (dir + 3) % 4;
    } else if (grid[r][c] == 'C') { // Clockwise: Up->Right(1), Right->Down(2), Down->Left(3), Left->Up(0)
        dir = (dir + 1) % 4;
    }

    // 2. Move step by step until blocked
    int nr = r, nc = c;
    while (true) {
        int next_r = nr + dr[dir];
        int next_c = nc + dc[dir];

        // Check if the next step is valid (within walls/grid and not obstacle)
        if (!isValid(next_r, next_c)) {
            break; // Blocked by wall or obstacle, stop at current position (nr, nc)
        }

        // Move to the next cell
        nr = next_r;
        nc = next_c;

        // Check for rotation plate at the new cell and update direction for subsequent steps
        if (grid[nr][nc] == 'A') {
            dir = (dir + 3) % 4; // Turn anti-clockwise
        } else if (grid[nr][nc] == 'C') {
            dir = (dir + 1) % 4; // Turn clockwise
        }
        // Continue moving in the (potentially new) direction
    }
    // Return the final resting position
    return {nr, nc};
}

// Function to perform all possible merges iteratively on the current set of robots.
// Modifies the vector in place.
void perform_merges(vector<Robot>& current_robots) {
    if (current_robots.size() < 2) return; // No merges possible with < 2 robots

    bool merged_in_pass = true;
    // Keep merging as long as a merge occurred in the previous pass
    while (merged_in_pass) {
        merged_in_pass = false;
        vector<Robot> next_round_robots;
        vector<bool> processed(current_robots.size(), false);
        // Sort robots primarily by position to group them for efficient checking
        sort(current_robots.begin(), current_robots.end(), [](const Robot& a, const Robot& b){
             return tie(a.r, a.c, a.min_l, a.max_l) < tie(b.r, b.c, b.min_l, b.max_l);
             });


        for (int i = 0; i < current_robots.size(); ++i) {
            if (processed[i]) continue; // Skip if already merged in this pass

            bool merged_robot_i = false;
            // Try merging robot 'i' with subsequent robots 'j' at the same location
            for (int j = i + 1; j < current_robots.size(); ++j) {
                 if (processed[j]) continue; // Skip if already merged

                 // Optimization: If robot j is at a different location, subsequent robots will also be (due to sorting)
                 if (current_robots[i].r != current_robots[j].r || current_robots[i].c != current_robots[j].c) {
                     break;
                 }

                 // Check compatibility (labels are consecutive)
                 if (current_robots[i].max_l + 1 == current_robots[j].min_l || current_robots[j].max_l + 1 == current_robots[i].min_l) {
                     // Merge robot i and j
                     Robot merged_robot;
                     merged_robot.min_l = min(current_robots[i].min_l, current_robots[j].min_l);
                     merged_robot.max_l = max(current_robots[i].max_l, current_robots[j].max_l);
                     merged_robot.r = current_robots[i].r; // Same location
                     merged_robot.c = current_robots[i].c;
                     next_round_robots.push_back(merged_robot); // Add merged robot to the next round list

                     processed[i] = true; // Mark both i and j as processed for this pass
                     processed[j] = true;
                     merged_in_pass = true; // Indicate that a merge occurred in this pass
                     merged_robot_i = true;
                     break; // Robot i has been merged, move to the next unprocessed robot
                 }
            }

             // If robot i wasn't merged with any subsequent robot in this pass, add it directly
            if (!processed[i]) {
                next_round_robots.push_back(current_robots[i]);
                processed[i] = true; // Mark as processed (even though not merged)
            }
        }
         // Update the robot list for the next pass or for finishing
        current_robots = next_round_robots;
         if (current_robots.size() < 2) break; // Stop if only 0 or 1 robot left
    }

     // Final sort for canonical representation before returning/using in set
    sort(current_robots.begin(), current_robots.end());
}


// Solves the problem using BFS
int solve() {
    // 1. Create the initial state vector
    vector<Robot> initial_state;
    for (int i = 0; i < N; ++i) {
        // Robot labels are 1 to N
        initial_state.push_back({i + 1, i + 1, initial_pos[i].first, initial_pos[i].second});
    }
    // Perform initial merges if any robots start at the same location (unlikely based on problem statement but safe)
    perform_merges(initial_state); // Sorts the state canonically

    // 2. Initialize BFS queue and visited set
    queue<pair<vector<Robot>, int>> q; // Stores pairs of (robot_state, pushes)
    set<vector<Robot>> visited;         // Stores visited robot_states (canonical form)

    // Add initial state to queue and visited set
    q.push({initial_state, 0});
    visited.insert(initial_state);

    // 3. Start BFS loop
    while (!q.empty()) {
        // Get current state from front of queue
        vector<Robot> current_robots = q.front().first;
        int current_pushes = q.front().second;
        q.pop();

        // 4. Goal Check: Check if only one robot remains and it spans labels 1 to N
        if (current_robots.size() == 1 && current_robots[0].min_l == 1 && current_robots[0].max_l == N) {
            return current_pushes; // Found the shortest path
        }

        // 5. Generate Next States: Iterate through each robot and each possible push direction
        for (int i = 0; i < current_robots.size(); ++i) {
            for (int dir_idx = 0; dir_idx < 4; ++dir_idx) { // 4 directions: 0=Up, 1=Right, 2=Down, 3=Left
                // Create a copy of the current state to modify
                vector<Robot> next_robots = current_robots;
                Robot moving_robot = next_robots[i]; // The robot being pushed
                int current_dir = dir_idx; // Make a copy of direction for simulation

                // Simulate the movement of the chosen robot
                pair<int, int> final_pos = simulate_move(moving_robot.r, moving_robot.c, current_dir);

                // Update the position of the moved robot in the 'next_robots' state
                next_robots[i].r = final_pos.first;
                next_robots[i].c = final_pos.second;

                // Perform all possible merges in the resulting configuration
                // This function modifies next_robots in place and sorts it canonically.
                perform_merges(next_robots);

                // 6. Check Visited and Enqueue: If the resulting state hasn't been visited
                if (visited.find(next_robots) == visited.end()) {
                    visited.insert(next_robots); // Mark as visited
                    q.push({next_robots, current_pushes + 1}); // Add to queue
                }
            }
        }
    }

    // 7. Goal Not Reachable: If the queue becomes empty and goal was not found
    return -1;
}

int main() {
    // Faster I/O
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    // Read input: N, W, H
    cin >> N >> W >> H;

    // Resize grid and initial position storage
    grid.resize(H);
    initial_pos.resize(N);
    vector<bool> pos_found(N, false); // To verify all robots are found

    // Read grid layout and find initial robot positions
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
        for (int j = 0; j < W; ++j) {
            if (isdigit(grid[i][j])) {
                int robot_label = grid[i][j] - '0'; // Get the digit value (1-9)
                int robot_id = robot_label - 1; // Convert to 0-indexed id

                if (robot_id >= 0 && robot_id < N) {
                   initial_pos[robot_id] = {i, j}; // Store initial position {row, col}
                   pos_found[robot_id] = true;
                   grid[i][j] = '.'; // Clear the robot's starting position on the grid map
                } else {
                    // Handle potential invalid input (e.g., label > N) if necessary
                     cerr << "Warning: Found digit '" << grid[i][j] << "' that is not a valid robot label (1-" << N << ")." << endl;
                     grid[i][j] = '.'; // Treat as empty space
                }
            }
        }
    }

     // Sanity check: Ensure all robots 1 to N were found in the input
    bool all_found = true;
    for(int i=0; i<N; ++i) {
        if (!pos_found[i]) {
            all_found = false;
            cerr << "Error: Robot " << (i+1) << " not found on the initial grid." << endl;
            // Depending on contest rules, might need to exit or handle differently
            // For robustness, let's assume valid input or return error code.
             return 1; // Indicate an error
        }
    }

    // Call the solver function and print the result
    cout << solve() << endl;

    return 0; // Indicate successful execution
}

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