| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1189247 | Zakir060 | Robots (APIO13_robots) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include <vector>
#include <string>
#include <queue>
// #include <map> // map əvəzinə unordered_map istifadə edəcəyik
#include <unordered_map> // Hash table əsaslı map
#include <set> // Lazım olarsa istifadə üçün qalsın
#include <algorithm>
#include <tuple>
#include <functional> // std::hash üçün lazımdır
using namespace std;
// --- Sabitlər və Qlobal Dəyişənlər ---
const int MAX_N = 9;
const int MAX_W = 50; // Maksimum ölçülər fərz edilir
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 (kanonikləşdirmə)
bool operator<(const Robot& other) const {
// Əsasən min_label görə sırala, qalanlar bərabərlik halında
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;
}
// unordered_map-də toqquşmaları həll etmək və elementləri müqayisə etmək üçün
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>; // Vəziyyət = robotların vektoru
// --- Hashing ---
// Sadə hash birləşdirmə funksiyası (boost::hash_combine kimi)
// Bu funksiya fərqli dəyərləri bir hash dəyərində birləşdirməyə kömək edir
template <class T>
inline void hash_combine(std::size_t& seed, const T& v) {
std::hash<T> hasher;
// Tipik hash birləşdirmə formulu
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// Robot üçün hash funksiyası
// std namespace daxilində ixtisaslaşdırma (specialization)
namespace std {
template <> struct hash<Robot> {
size_t operator()(const Robot& r) const {
size_t seed = 0;
// Robotun bütün vacib üzvlərinin hash-lərini birləşdir
hash_combine(seed, r.min_label);
hash_combine(seed, r.max_label);
hash_combine(seed, r.r);
hash_combine(seed, r.c);
return seed;
}
};
// State (vector<Robot>) üçün hash funksiyası
// VACİB: Bu funksiya fərz edir ki, vektor hash-lənmədən ƏVVƏL sıralanıb (kanonikləşdirilib)!
template <> struct hash<State> {
size_t operator()(const State& s) const {
size_t seed = 0;
// Vektordakı hər bir robotun hash-ini birləşdir
for (const auto& robot : s) {
hash_combine(seed, robot); // hash<Robot> istifadə edir
}
return seed;
}
};
} // namespace std
// --- 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'; // Sərhəddən kənar = maneə
return grid[r][c];
}
// --- Hərəkət Simulyasiyası (simulate_move - dəyişməz) ---
int dr[] = {-1, 0, 1, 0}; // Yuxarı(0), Sağ(1), Aşağı(2), Sol(3)
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; // Robotun hərəkət etmək istədiyi ilkin istiqamət
// Başlanğıcda fırlanan lövhə varsa, hərəkət istiqamətini dəyiş
char start_plate = get_grid_char(r, c);
if (start_plate == 'A') { // Saat əqrəbinin əksi
current_dir = (push_dir + 3) % 4;
} else if (start_plate == 'C') { // Saat əqrəbi istiqaməti
current_dir = (push_dir + 1) % 4;
}
// Addım-addım hərəkət simulyasiyası
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);
// Divar və ya maneə ilə toqquşma yoxlanışı
if (next_cell == 'x' || !is_valid(next_r, next_c)) {
break; // Cari (r, c) mövqeyində dayan
}
// Növbəti xanaya keç
r = next_r;
c = next_c;
// Əgər yeni xanada fırlanan lövhə varsa, növbəti addım üçün istiqaməti dəyiş
if (next_cell == 'A') {
current_dir = (current_dir + 3) % 4;
} else if (next_cell == 'C') {
current_dir = (current_dir + 1) % 4;
}
}
return {r, c}; // Son mövqeyi qaytar
}
// --- Birləşmə Məntiqi (merge_robots_at_location - kiçik optimizasiya) ---
// Optimallaşdırma: const referans ilə ötür, nəticəni qaytar.
// Eyni yerdəki robotları birləşdirir
State merge_robots_at_location(const State& robots_at_loc) {
if (robots_at_loc.size() <= 1) {
return robots_at_loc; // Birləşmə mümkün deyil
}
State current_robots = robots_at_loc;
// Ehtiyac olarsa burada bir dəfə sıralamaq olar, amma çağıran tərəf
// hər bir mövqe üçün sıralanmış giriş təmin edə bilər.
// sort(current_robots.begin(), current_robots.end());
bool merged; // Bu iterasiyada birləşmə oldumu?
do {
merged = false;
if (current_robots.size() <= 1) break; // Əgər 1 və ya 0 robot qalıbsa tez çıx
State next_robots; // Növbəti iterasiya üçün robotlar
vector<bool> used(current_robots.size(), false); // Hansı robotların artıq birləşdiyi
for (int i = 0; i < current_robots.size(); ++i) {
if (used[i]) continue;
// i-ci robotu sonrakı j robotları ilə birləşdirməyə çalış
bool i_merged_this_pass = false;
for (int j = i + 1; j < current_robots.size(); ++j) {
if (used[j]) continue;
// Uyğunluq yoxlanışı (r, c eyni olmalıdır, bu funksiyanın çağırılma qaydası ilə təmin edilir)
if (current_robots[i].max_label + 1 == current_robots[j].min_label) {
// i və j-ni birləşdir
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; // Hər ikisini istifadə edilmiş kimi işarələ
merged = i_merged_this_pass = true; // Birləşmə oldu
break; // i robotu birləşdi, növbəti i-yə keç
} else if (current_robots[j].max_label + 1 == current_robots[i].min_label) {
// j və i-ni birləşdir
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;
}
}
// Əgər i robotu bu iterasiyada heç nə ilə birləşmədisə, onu növbəti vəziyyətə əlavə et
if (!i_merged_this_pass) {
// Yoxla ki, əvvəlki bir robotla birləşərək used işarələnməyib
if(!used[i]) {
next_robots.push_back(current_robots[i]);
}
}
}
current_robots = next_robots; // Robot siyahısını yenilə
// Birləşmə sıranı poza biləcəyi üçün yenidən sıralamaq vacibdir (min_label görə)
sort(current_robots.begin(), current_robots.end());
} while (merged); // Birləşmə baş verdiyi müddətcə təkrarla
return current_robots;
}
// --- Kanonikləşdirmə (dəyişməz, amma hashing/axtarışdan əvvəl vacibdir) ---
// Vəziyyəti robotları sıralayaraq kanonik formaya salır
State canonicalize(State s) {
sort(s.begin(), s.end());
return s;
}
// --- BFS (unordered_map istifadə edərək) ---
int solve() {
// 1. İlkin vəziyyəti tap
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});
}
}
}
// Map/queue-ya əlavə etmədən ƏVVƏL BİR DƏFƏ kanonikləşdir
initial_state = canonicalize(initial_state);
// 2. BFS üçün strukturları başlat
queue<State> q; // Ziyarət ediləcək vəziyyətlər növbəsi
// Daha sürətli axtarış üçün unordered_map istifadə et
unordered_map<State, int> dist; // Vəziyyət -> minimum itələmə sayı
q.push(initial_state);
dist[initial_state] = 0; // İlkin vəziyyətin məsafəsi 0-dır
// 3. BFS döngüsü
while (!q.empty()) {
// State obyektini kopyalamaq əvəzinə std::move istifadə etmək olar,
// amma sadəlik üçün kopyalama saxlayaq.
State current_state = q.front(); // Növbədən vəziyyəti götür (kopyalanır)
q.pop();
int current_dist = dist[current_state]; // Məsafəni unordered_map-dən tap
// Hədəf vəziyyət yoxlanışı
if (current_state.size() == 1 && current_state[0].min_label == 1 && current_state[0].max_label == N) {
return current_dist; // Həll tapıldı
}
// Mümkün hərəkətləri (hər robotu 4 istiqamətdə itələmək) yoxla
for (int i = 0; i < current_state.size(); ++i) { // Cari vəziyyətdəki hər robot üçün
Robot robot_to_move = current_state[i]; // Hərəkət etdiriləcək robotun kopyası
for (int push_dir = 0; push_dir < 4; ++push_dir) { // Hər itələmə istiqaməti üçün
// Hərəkəti simulyasiya et
pair<int, int> final_pos = simulate_move(robot_to_move.r, robot_to_move.c, push_dir);
// Əgər robot heç yerə hərəkət etməyibsə, bu itələməni ötür
// Bu, eyni vəziyyətin təkrar yaranmasının qarşısını alır
if (final_pos.first == robot_to_move.r && final_pos.second == robot_to_move.c) {
continue;
}
// --- Növbəti vəziyyəti yarat ---
// Robotları mövqelərinə görə qruplaşdırmaq üçün map istifadə et
map<pair<int,int>, State> robots_by_location;
// Hərəkət edən robotdan BAŞQA bütün robotları map-ə əlavə et
for(int k=0; k < current_state.size(); ++k) {
if (k == i) continue; // Hərəkət edən robotu ötür
const auto& other_robot = current_state[k];
robots_by_location[{other_robot.r, other_robot.c}].push_back(other_robot);
}
// Hərəkət etmiş robotu YENİ mövqesinə görə map-ə əlavə et
Robot moved_robot_instance = robot_to_move; // Mövqeyi dəyişmək üçün kopya götür
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);
// --- Birləşməni həyata keçir və son vəziyyəti qur ---
State final_next_state_unmerged; // Kanonikləşdirmədən əvvəl müvəqqəti
for(auto& location_pair : robots_by_location) {
// Hər bir mövqedəki robotları birləşdirmədən əvvəl sırala (əgər merge funksiyası sıralanmış giriş tələb edirsə)
sort(location_pair.second.begin(), location_pair.second.end());
State merged_robots = merge_robots_at_location(location_pair.second);
// Birləşmə nəticələrini yekun vəziyyətə əlavə et
final_next_state_unmerged.insert(final_next_state_unmerged.end(), merged_robots.begin(), merged_robots.end());
}
// --- Kanonikləşdir və ziyarət edilibmi yoxla ---
State final_next_state = canonicalize(final_next_state_unmerged); // Yekun robot siyahısını sırala
// unordered_map-in 'find' metodunu istifadə et
if (dist.find(final_next_state) == dist.end()) { // Əgər bu vəziyyət ziyarət edilməyibsə
dist[final_next_state] = current_dist + 1; // Yeni məsafəni qeyd et (unordered_map-ə daxil et)
q.push(final_next_state); // Kanonik vəziyyəti növbəyə əlavə et
}
}
}
}
return -1; // Növbə boşaldı və hədəf tapılmadı
}
// --- Main Funksiyası (dəyişməz) ---
int main() {
// C++ I/O optimallaşdırılması
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Girişi oxu
cin >> N >> W >> H;
grid.resize(H);
for (int i = 0; i < H; ++i) {
cin >> grid[i];
}
// Problemi həll et
int result = solve();
// Nəticəni çap et
cout << result << endl;
return 0;
}