Submission #1188236

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

robots

#include <iostream>
#include <vector>
#include <string>
#include <queue>
// #include <set> // No longer needed
#include <unordered_set> // Use unordered_set for visited states
#include <map>
#include <tuple>   // For std::tie used in comparison
#include <vector>
#include <algorithm> // For std::sort
#include <cctype>    // For std::isdigit
#include <functional> // For std::hash

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 (needed for canonical state representation)
    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 unordered_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);
    }
};

// --- Hashing Implementation ---

// Helper function to combine hashes (based on boost::hash_combine)
template <class T>
inline void hash_combine(size_t& seed, const T& v) {
    hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

// Hash function for Robot struct
struct RobotHash {
    size_t operator()(const Robot& r) const {
        size_t seed = 0;
        hash_combine(seed, r.min_l);
        hash_combine(seed, r.max_l);
        hash_combine(seed, r.r);
        hash_combine(seed, r.c);
        return seed;
    }
};

// Hash function for vector<Robot>
// IMPORTANT: Assumes the vector<Robot> is already sorted into canonical form!
struct VectorRobotHash {
     size_t operator()(const vector<Robot>& robots) const {
         size_t seed = robots.size(); // Start seed with size
         RobotHash robot_hasher;
         for(const auto& r : robots) {
             // Combine hash of each robot into the seed
             seed ^= robot_hasher(r) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
         }
         return seed;
     }
};


// --- Constants and Global Variables ---
const int MAX_H = 501;
const int MAX_W = 501;

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

int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};

pair<int, int> precomputed_moves[MAX_H][MAX_W][4];

// Function to check if a cell is valid
bool isValid(int r, int c) {
    return r >= 0 && r < H && c >= 0 && c < W && grid[r][c] != 'x';
}

// Precomputation Function (No changes needed here)
void precompute_all_moves() {
    for (int r = 0; r < H; ++r) {
        for (int c = 0; c < W; ++c) {
            if (grid[r][c] == 'x') {
                 for (int start_dir = 0; start_dir < 4; ++start_dir) precomputed_moves[r][c][start_dir] = {-1, -1};
                 continue;
            }
            for (int start_dir = 0; start_dir < 4; ++start_dir) {
                int nr = r, nc = c;
                int current_dir = start_dir;
                bool starting_on_rotator = (grid[r][c] == 'A' || grid[r][c] == 'C');
                int first_step_dir = start_dir;
                if (starting_on_rotator) {
                    int rotated_dir = (grid[r][c] == 'A') ? (start_dir + 3) % 4 : (start_dir + 1) % 4;
                    int rotated_next_r = r + dr[rotated_dir];
                    int rotated_next_c = c + dc[rotated_dir];
                    if (isValid(rotated_next_r, rotated_next_c)) {
                        first_step_dir = rotated_dir;
                    }
                }
                int first_step_r = r + dr[first_step_dir];
                int first_step_c = c + dc[first_step_dir];
                if (!isValid(first_step_r, first_step_c)) {
                    precomputed_moves[r][c][start_dir] = {r, c};
                    continue;
                }
                nr = first_step_r; nc = first_step_c;
                current_dir = first_step_dir;
                while (true) {
                    if (grid[nr][nc] == 'A') current_dir = (current_dir + 3) % 4;
                    else if (grid[nr][nc] == 'C') current_dir = (current_dir + 1) % 4;
                    int next_r = nr + dr[current_dir];
                    int next_c = nc + dc[current_dir];
                    if (!isValid(next_r, next_c)) break;
                    nr = next_r; nc = next_c;
                }
                precomputed_moves[r][c][start_dir] = {nr, nc};
            }
        }
    }
}


// Optimized simulate_move using precomputation
pair<int, int> simulate_move(int r, int c, int dir) {
     return precomputed_moves[r][c][dir];
}

// Function to perform merges (No changes needed here)
// IMPORTANT: This function sorts the vector at the end, which is required for hashing.
void perform_merges(vector<Robot>& current_robots) {
     if (current_robots.size() < 2) return;
     bool merged_in_pass = true;
     while (merged_in_pass) {
         merged_in_pass = false;
         vector<Robot> next_round_robots;
         vector<bool> processed(current_robots.size(), false);
         // Sort by position first to efficiently find robots at the same location
         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;
             bool merged_robot_i = false;
             // Check subsequent robots ONLY if they are at the same location
             for (int j = i + 1; j < current_robots.size(); ++j) {
                  if (processed[j]) continue;
                  // Optimization: If position differs, no more robots at location i can be found
                  if (current_robots[i].r != current_robots[j].r || current_robots[i].c != current_robots[j].c) break;

                  // Check compatibility
                  if (current_robots[i].max_l + 1 == current_robots[j].min_l || current_robots[j].max_l + 1 == current_robots[i].min_l) {
                      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;
                      merged_robot.c = current_robots[i].c;
                      next_round_robots.push_back(merged_robot);
                      processed[i] = true; processed[j] = true;
                      merged_in_pass = true; merged_robot_i = true;
                      break; // Robot i merged, move to next i
                  }
             }
             // If robot i wasn't processed (didn't merge), add it back
             if (!processed[i]) {
                 next_round_robots.push_back(current_robots[i]);
                 processed[i] = true; // Mark as processed (kept)
             }
         }
         current_robots = next_round_robots; // Update for next pass
          if (current_robots.size() < 2) break; // Stop if few robots left
     }
     // Final sort by labels/pos for canonical representation before hashing/storing
     sort(current_robots.begin(), current_robots.end());
 }


// Solves the problem using BFS with precomputed moves and hashing
int solve() {
    vector<Robot> initial_state;
    for (int i = 0; i < N; ++i) {
        initial_state.push_back({i + 1, i + 1, initial_pos[i].first, initial_pos[i].second});
    }
    perform_merges(initial_state); // Sorts the state canonically

    queue<pair<vector<Robot>, int>> q;
    // *** Use unordered_set with custom hash function ***
    unordered_set<vector<Robot>, VectorRobotHash> visited;

    q.push({initial_state, 0});
    visited.insert(initial_state); // Insert requires state to be sorted

    while (!q.empty()) {
        vector<Robot> current_robots = q.front().first; // Copy state
        int current_pushes = q.front().second;
        q.pop();

        // Goal check
        if (current_robots.size() == 1 && current_robots[0].min_l == 1 && current_robots[0].max_l == N) {
            return current_pushes;
        }

        // Generate next states
        for (int i = 0; i < current_robots.size(); ++i) {
            for (int dir_idx = 0; dir_idx < 4; ++dir_idx) {
                // It's often faster to modify a copy than to create a new vector each time
                vector<Robot> next_robots = current_robots;
                Robot moving_robot = next_robots[i]; // Get robot to move (before potential modification)

                pair<int, int> final_pos = simulate_move(moving_robot.r, moving_robot.c, dir_idx);

                if (final_pos.first == -1) continue; // Invalid start pos for move

                // Update the specific robot that moved
                next_robots[i].r = final_pos.first;
                next_robots[i].c = final_pos.second;

                // Perform merges. This sorts the vector `next_robots` canonically.
                perform_merges(next_robots);

                // Check visited using unordered_set's find (average O(1) + hashing cost)
                if (visited.find(next_robots) == visited.end()) {
                    visited.insert(next_robots); // Insert requires state to be sorted
                    q.push({next_robots, current_pushes + 1});
                }
            }
        }
    }
    return -1; // Goal not reachable
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> W >> H;

    grid.resize(H);
    initial_pos.resize(N);
    vector<bool> pos_found(N, false);

    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';
                int robot_id = robot_label - 1;
                if (robot_id >= 0 && robot_id < N) {
                   initial_pos[robot_id] = {i, j};
                   pos_found[robot_id] = true;
                   grid[i][j] = '.';
                } else {
                     grid[i][j] = '.';
                }
            }
        }
    }

    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;
             return 1;
        }
    }

    precompute_all_moves();
    cout << solve() << endl;

    return 0;
}

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