Submission #1189252

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189252		Zakir060	Robots (APIO13_robots)	C++20	30 / 100	1589 ms	55780 KiB

robots

#include <iostream>
#include <vector>
#include <string>
#include <queue> // priority_queue üçün
#include <map>
#include <set>
#include <algorithm>
#include <tuple>
#include <functional> // std::greater üçün
#include <cmath> // min/max üçün

using namespace std;

// --- Sabitlər, Qlobal Dəyişənlər, Robot strukturu, State typedef (dəyişməz) ---
const int MAX_N = 9;
const int MAX_W = 50;
const int MAX_H = 50;
int N, W, H;
vector<string> grid;

struct Robot {
    int min_label; int max_label; int r; int c;
    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; }
    bool operator==(const Robot& other) const { return min_label == other.min_label && max_label == other.max_label && r == other.r && c == other.c; }
};
using State = vector<Robot>;

// --- Köməkçi Funksiyalar (is_valid, get_grid_char, simulate_move - 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]; }
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};
}

// --- YENİ Birləşmə Məntiqi ---
State merge_robots_at_location(const State& robots_at_loc) { // _v2 adını standartlaşdırdıq
    if (robots_at_loc.size() <= 1) {
        return robots_at_loc;
    }
    State current_robots = robots_at_loc;
    // Başlanğıcda sıralamaq vacibdir (çağıran tərəf sıralı verməsə belə)
    sort(current_robots.begin(), current_robots.end());

    while (true) { // Bir iterasiyada heç bir birləşmə olmayana qədər davam et
        bool merged_in_pass = false;
        State next_robots; // Növbəti iterasiya üçün robotlar
        vector<bool> used(current_robots.size(), false); // Bu iterasiyada istifadə edilənlər

        if (current_robots.size() <= 1) { break; } // Əgər 1 və ya 0 robot qalıbsa, bitir

        // Birləşmələri tap
        for (int i = 0; i < current_robots.size(); ++i) {
            if (used[i]) continue; // Əgər bu robot artıq başqası ilə birləşibsə, ötür

            int merge_partner_j = -1; // i ilə birləşəcək ilk j-nin indeksi
            for (int j = i + 1; j < current_robots.size(); ++j) {
                 if (used[j]) continue; // Əgər j də artıq başqası ilə birləşibsə, ötür

                 // Uyğunluq yoxlanışı
                 if (current_robots[i].max_label + 1 == current_robots[j].min_label) {
                     merge_partner_j = j; break;
                 } else if (current_robots[j].max_label + 1 == current_robots[i].min_label) {
                     merge_partner_j = j; break;
                 }
            }

            if (merge_partner_j != -1) { // i üçün birləşmə partnyoru tapıldı
                int j = merge_partner_j;
                // Düzgün min/max label ilə yeni robot yarat
                 int final_min = min(current_robots[i].min_label, current_robots[j].min_label);
                 int final_max = max(current_robots[i].max_label, current_robots[j].max_label);
                 // Yeni robotu növbəti siyahıya əlavə et (mövqe i-dən götürülür, onsuz da eynidir)
                 next_robots.push_back({final_min, final_max, current_robots[i].r, current_robots[i].c});
                 // i və j-ni istifadə edilmiş kimi işarələ
                 used[i] = true;
                 used[j] = true;
                 merged_in_pass = true; // Bu iterasiyada birləşmə oldu
            }
        }

        // Bu iterasiyada birləşməyən robotları növbəti siyahıya əlavə et
        for(int i=0; i<current_robots.size(); ++i) {
            if (!used[i]) {
                next_robots.push_back(current_robots[i]);
            }
        }

        // Əgər bütün pass boyunca heç bir birləşmə olmadısa, döngədən çıx
        if (!merged_in_pass) {
            break;
        }

        // Növbəti iterasiya üçün siyahını yenilə və sırala
        current_robots = next_robots;
        sort(current_robots.begin(), current_robots.end());
    }
    return current_robots; // Son nəticəni qaytar
}


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

// --- A* Heuristika (dəyişməz) ---
int calculate_heuristic(const State& s) { if (s.empty()) return 0; return max(0, (int)s.size() - 1); }

// --- A* Axtarış (yeni birləşmə funksiyası ilə) ---
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);

    using PQElement = tuple<int, int, State>;
    priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pq;
    map<State, int> g_costs; // Vəziyyət -> minimum g dəyəri (itələmə sayı)

    int initial_g = 0; int initial_h = calculate_heuristic(initial_state); int initial_f = initial_g + initial_h;
    pq.push({initial_f, initial_g, initial_state});
    g_costs[initial_state] = initial_g;

    while (!pq.empty()) {
        auto [current_f, current_g, current_state] = pq.top(); pq.pop();

        // Prioritet növbəsindən çıxarılan vəziyyət üçün artıq daha yaxşı yol tapılıbsa, ötür
        // Bu yoxlama vacibdir, çünki eyni vəziyyət növbəyə fərqli g dəyərləri ilə düşə bilər
        // find() istifadə edərək daha təhlükəsiz yoxlamaq olar
        auto g_it = g_costs.find(current_state);
        if (g_it == g_costs.end() || current_g > g_it->second) {
             continue;
        }

        // Hədəf yoxlanışı
        if (current_state.size() == 1 && current_state[0].min_label == 1 && current_state[0].max_label == N) {
            return current_g; // Optimal həll tapıldı
        }

        // Qonşu vəziyyətləri (hərəkətləri) generasiya et
        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; } // Hərəkətsiz itələməni ötür

                // Növbəti vəziyyəti yarat (robotları mövqeyə görə qruplaşdır)
                map<pair<int,int>, State> robots_by_location;
                for(int k=0; k < current_state.size(); ++k) { if (k == i) continue; const auto& orob = current_state[k]; robots_by_location[{orob.r, orob.c}].push_back(orob); }
                Robot moved_robot = robot_to_move; moved_robot.r = final_pos.first; moved_robot.c = final_pos.second;
                robots_by_location[{moved_robot.r, moved_robot.c}].push_back(moved_robot);

                // Hər mövqedə birləşməni apar
                State next_state_unmerged;
                for(auto& loc_pair : robots_by_location) {
                    // Yeni birləşmə funksiyasını istifadə et
                    State merged = merge_robots_at_location(loc_pair.second); // _v2 yazmaq lazım deyil, adını standartlaşdırdıq
                    next_state_unmerged.insert(next_state_unmerged.end(), merged.begin(), merged.end());
                }

                // Növbəti vəziyyəti kanonikləşdir
                State next_state = canonicalize(next_state_unmerged);

                // Növbəti vəziyyət üçün dəyərləri hesabla
                int next_g = current_g + 1;
                int next_h = calculate_heuristic(next_state);
                int next_f = next_g + next_h;

                // Bu vəziyyətə daha qısa yol tapılıbsa və ya yeni vəziyyətdirsə, yenilə/əlavə et
                auto existing_g_it = g_costs.find(next_state);
                if (existing_g_it == g_costs.end() || next_g < existing_g_it->second) {
                    g_costs[next_state] = next_g; // Minimum g dəyərini yenilə
                    pq.push({next_f, next_g, next_state}); // Prioritet növbəsinə əlavə et
                }
            }
        }
    }
    return -1; // Hədəfə çatmaq mümkün olmadı
}

// --- 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