Submission #1189336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189336		xumoyun_akromov1	Robots (APIO13_robots)	C++17	30 / 100	1597 ms	69136 KiB

robots

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map> // <--- unordered_map əvəzinə map istifadə edirik
#include <set>
#include <algorithm>
#include <tuple>
#include <functional> // Artıq hash üçün lazım deyil, amma qala bilər

using namespace std;

// --- Sabitlər və Qlobal Dəyişənlər ---
const int MAX_N = 9;
const int MAX_W = 50;
const int MAX_H = 50;
int N, W, H;
vector<string> grid;


// --- Robot Təsviri ---
struct Robot {
    int min_label;
    int max_label;
    int r, c;

    // Sıralama üçün (map üçün vacibdir)
    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;
    }

    // Bərabərlik (map üçün lazım deyil, amma zərər vermir)
    bool operator==(const Robot& other) const {
        return min_label == other.min_label &&
               max_label == other.max_label &&
               r == other.r &&
               c == other.c;
    }
};

// --- Vəziyyət Təsviri ---
using State = vector<Robot>; // State = vector<Robot>, map<State,...> üçün operator< təyin olunmalıdır (vector bunu təmin edir)


// --- Hash funksiyaları artıq lazım deyil ---
/*
template <class T>
inline void hash_combine(std::size_t& seed, const T& v) { ... }
namespace std {
template <> struct hash<Robot> { ... };
}
struct StateHash { ... };
*/

// --- Köməkçi Funksiyalar (is_valid, get_grid_char - dəyişməz) ---
bool is_valid(int r, int c) { return r >= 0 && r < H && c >= 0 && c < W; }
char get_grid_char(int r, int c) { if (!is_valid(r, c)) return 'x'; return grid[r][c]; }


// --- Hərəkət Simulyasiyası (simulate_move - dəyişməz) ---
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
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;
    char start_plate = get_grid_char(r, c);
    if (start_plate == 'A') { current_dir = (push_dir + 3) % 4; }
    else if (start_plate == 'C') { current_dir = (push_dir + 1) % 4; }
    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);
        if (next_cell == 'x' || !is_valid(next_r, next_c)) { break; }
        r = next_r; c = next_c;
        if (next_cell == 'A') { current_dir = (current_dir + 3) % 4; }
        else if (next_cell == 'C') { current_dir = (current_dir + 1) % 4; }
    } return {r, c};
}

// --- Birləşmə Məntiqi (merge_robots_at_location - dəyişməz) ---
State merge_robots_at_location(const State& robots_at_loc) {
    if (robots_at_loc.size() <= 1) return robots_at_loc;
    State current_robots = robots_at_loc;
    bool merged;
    do {
        merged = false;
        if (current_robots.size() <= 1) break;
        State next_robots;
        vector<bool> used(current_robots.size(), false);
        // Birləşmədən əvvəl sıralamaq yaxşı praktikadır, amma State onsuz da sıralı gəlməlidir
         sort(current_robots.begin(), current_robots.end());

        for (int i = 0; i < current_robots.size(); ++i) {
            if (used[i]) continue;
            bool i_merged_this_pass = false;
            for (int j = i + 1; j < current_robots.size(); ++j) {
                if (used[j]) continue;
                if (current_robots[i].max_label + 1 == current_robots[j].min_label) {
                    next_robots.push_back({current_robots[i].min_label, current_robots[j].max_label, current_robots[i].r, current_robots[i].c});
                    used[i] = used[j] = true; merged = i_merged_this_pass = true; break;
                } else if (current_robots[j].max_label + 1 == current_robots[i].min_label) {
                     next_robots.push_back({current_robots[j].min_label, current_robots[i].max_label, current_robots[i].r, current_robots[i].c});
                    used[i] = used[j] = true; merged = i_merged_this_pass = true; break;
                }
            }
            if (!i_merged_this_pass && !used[i]) { next_robots.push_back(current_robots[i]); }
        }
        current_robots = next_robots;
        // Növbəti dövr üçün sıralamaq vacibdir
        sort(current_robots.begin(), current_robots.end());
    } while (merged);
    return current_robots;
}


// --- Kanonikləşdirmə (dəyişməz, map üçün də vacibdir) ---
State canonicalize(State s) {
    sort(s.begin(), s.end());
    return s;
}

// --- Breadth-First Search (BFS) - map istifadə edərək ---
int solve() {
    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);

    queue<State> q;
    // map istifadə edirik. Açar (State) üçün operator< təyin olunmalıdır.
    // vector üçün bu operator standart olaraq təyin edilib (elementləri müqayisə edir).
    map<State, int> dist;

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

    while (!q.empty()) {
        State current_state = q.front();
        q.pop();

        // map-də find istifadə etmək daha robustdur, amma operator[] də işləyir
        int current_dist = dist[current_state];

        if (current_state.size() == 1 && current_state[0].min_label == 1 && current_state[0].max_label == N) {
            return current_dist;
        }

        for (int i = 0; i < current_state.size(); ++i) {
            Robot robot_to_move = current_state[i];
            for (int push_dir = 0; push_dir < 4; ++push_dir) {
                pair<int, int> final_pos = simulate_move(robot_to_move.r, robot_to_move.c, push_dir);
                if (final_pos.first == robot_to_move.r && final_pos.second == robot_to_move.c) { continue; }

                // Növbəti vəziyyəti qruplaşdır/birləşdir (Burada map istifadəsi doğrudur)
                map<pair<int,int>, State> robots_by_location; // Bu map açar olaraq State istifadə etmir
                for(int k=0; k < current_state.size(); ++k) {
                    if (k == i) continue;
                    const auto& other_robot = current_state[k];
                    robots_by_location[{other_robot.r, other_robot.c}].push_back(other_robot);
                }
                Robot moved_robot_instance = robot_to_move;
                moved_robot_instance.r = final_pos.first; moved_robot_instance.c = final_pos.second;
                robots_by_location[{moved_robot_instance.r, moved_robot_instance.c}].push_back(moved_robot_instance);

                State final_next_state_unmerged;
                for(auto& location_pair : robots_by_location) {
                    sort(location_pair.second.begin(), location_pair.second.end());
                    State merged_robots = merge_robots_at_location(location_pair.second);
                    final_next_state_unmerged.insert(final_next_state_unmerged.end(), merged_robots.begin(), merged_robots.end());
                }

                // map-də istifadə etməzdən əvvəl KANONİKLƏŞDİR
                State final_next_state = canonicalize(final_next_state_unmerged);

                // map üçün find istifadə et
                if (dist.find(final_next_state) == dist.end()) {
                    dist[final_next_state] = current_dist + 1;
                    q.push(final_next_state);
                }
            }
        }
    }

    return -1;
}

// --- Main Funksiyası (dəyişməz) ---
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> W >> H; grid.resize(H);
    for (int i = 0; i < H; ++i) { cin >> grid[i]; }
    int result = solve(); cout << result << endl;
    return 0;
}

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