Submission #1189248

#TimeUsernameProblemLanguageResultExecution timeMemory
1189248Zakir060Robots (APIO13_robots)C++20
Compilation error
0 ms0 KiB
#include <iostream> #include <vector> #include <string> #include <queue> #include <unordered_map> // Bu qalır #include <set> #include <algorithm> #include <tuple> #include <functional> // std::hash üçün (Robot və hash_combine üçün) 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 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 yoxlanışı üçün (unordered_map üçün vacib) 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>; // --- Hashing İnfrastrukturu --- // Hash birləşdirmə köməkçi funksiyası template <class T> inline void hash_combine(std::size_t& seed, const T& v) { std::hash<T> hasher; seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); } // Robot üçün hash funksiyası (std daxilində ixtisaslaşma adətən işləyir) namespace std { template <> struct hash<Robot> { size_t operator()(const Robot& r) const { size_t seed = 0; hash_combine(seed, r.min_label); hash_combine(seed, r.max_label); hash_combine(seed, r.r); hash_combine(seed, r.c); return seed; } }; } // namespace std // State (vector<Robot>) üçün hash funktor - std NAMESPACE XARİCİNDƏ struct StateHash { // VACİB: Fərz edilir ki, bu operatora ötürülən 's' State obyekti // ƏVVƏLCƏDƏN SIRALANIB (kanonikləşdirilib)! size_t operator()(const State& s) const { size_t seed = 0; // hash_combine daxilində std::hash<Robot> avtomatik tapılmalıdır for (const auto& robot : s) { hash_combine(seed, robot); } return seed; } }; // --- 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) --- // Əvvəlki versiyadakı kimi qaldığını fərz edək 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); 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; } } // Əgər i robotu bu dövrdə birləşmədisə və əvvəlcədən istifadə edilməyibsə, onu əlavə et if (!i_merged_this_pass && !used[i]) { next_robots.push_back(current_robots[i]); } } current_robots = next_robots; sort(current_robots.begin(), current_robots.end()); // Birləşmədən sonra sırala } while (merged); return current_robots; } // --- Kanonikləşdirmə (dəyişməz) --- State canonicalize(State s) { sort(s.begin(), s.end()); return s; } // --- Breadth-First Search (BFS) --- int solve() { State initial_state; // İlkin vəziyyəti tap (dəyişməz) 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}); } } } // Kanonikləşdir initial_state = canonicalize(initial_state); queue<State> q; // unordered_map-i xüsusi StateHash funktorunu göstərərək təyin et // Üçüncü template arqumenti hash funktorunun tipidir unordered_map<State, int, StateHash> dist; q.push(initial_state); dist[initial_state] = 0; while (!q.empty()) { State current_state = q.front(); q.pop(); // dist-dən məsafəni alarkən ehtiyatlı olmaq lazımdır, əgər map istifadə ediriksə. // unordered_map-də find istifadə etmək daha təhlükəsizdir. // int current_dist = dist[current_state]; // Bu, element yoxdursa yeni element yarada bilər auto it = dist.find(current_state); if (it == dist.end()) { // Bu hal baş verməməlidir, çünki növbəyə yalnız dist-də olanlar əlavə edilir continue; } int current_dist = it->second; 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ıraraq/birləşdirərək yarat (dəyişməz) map<pair<int,int>, State> robots_by_location; 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) { // Birləşmədən əvvəl sırala 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()); } // unordered_map-də istifadə etməzdən əvvəl KANONİKLƏŞDİR State final_next_state = canonicalize(final_next_state_unmerged); // Axtarış üçün 'find' istifadə et if (dist.find(final_next_state) == dist.end()) { dist[final_next_state] = current_dist + 1; // Daxil et q.push(final_next_state); // Kanonik vəziyyəti növbəyə əlavə et } } } } 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; }

Compilation message (stderr)

robots.cpp: In function 'int solve()':
robots.cpp:192:17: error: 'map' was not declared in this scope
  192 |                 map<pair<int,int>, State> robots_by_location;
      |                 ^~~
robots.cpp:8:1: note: 'std::map' is defined in header '<map>'; did you forget to '#include <map>'?
    7 | #include <algorithm>
  +++ |+#include <map>
    8 | #include <tuple>
robots.cpp:192:34: error: expected primary-expression before ',' token
  192 |                 map<pair<int,int>, State> robots_by_location;
      |                                  ^
robots.cpp:192:41: error: expected primary-expression before '>' token
  192 |                 map<pair<int,int>, State> robots_by_location;
      |                                         ^
robots.cpp:192:43: error: 'robots_by_location' was not declared in this scope; did you mean 'merge_robots_at_location'?
  192 |                 map<pair<int,int>, State> robots_by_location;
      |                                           ^~~~~~~~~~~~~~~~~~
      |                                           merge_robots_at_location