#include <iostream>
#include <vector>
#include <string>
#include <queue> // Need priority_queue
#include <map>
#include <set>
#include <algorithm>
#include <tuple>
#include <functional>
using namespace std;
// --- Constants, Globals, Robot struct, State typedef (unchanged) ---
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 { /* ... unchanged ... */
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 { /* ... unchanged ... */
return min_label == other.min_label && max_label == other.max_label && r == other.r && c == other.c;
}
};
using State = vector<Robot>;
// --- Helper Functions (is_valid, get_grid_char, simulate_move, merge_robots_at_location, canonicalize - unchanged) ---
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) { /* ... unchanged ... */
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};
}
State merge_robots_at_location(const State& robots_at_loc) { /* ... unchanged (using the safer map version) ... */
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);
sort(current_robots.begin(), current_robots.end()); // Ensure sorted for reliable merging check
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; sort(current_robots.begin(), current_robots.end());
} while (merged); return current_robots;
}
State canonicalize(State s) { sort(s.begin(), s.end()); return s; }
// --- A* Heuristic ---
int calculate_heuristic(const State& s) {
// h = number of robot groups - 1
// Goal is 1 group, so need at least size-1 merges.
if (s.empty()) return 0; // Or some large value? Should not happen.
return max(0, (int)s.size() - 1);
}
// --- A* Search ---
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);
// Priority Queue for A*: Stores { f_cost, g_cost, state }
// We want the minimum f_cost, so use std::greater for min-heap.
using PQElement = tuple<int, int, State>;
priority_queue<PQElement, vector<PQElement>, greater<PQElement>> pq;
// Map to store the minimum g_cost (pushes) found so far to reach a state
map<State, int> g_costs;
// Initial state
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();
// If we found a shorter path to this state already, ignore this one
// Check required because priority queue might hold multiple entries for the same state
// with different costs discovered at different times.
if (current_g > g_costs[current_state]) {
continue;
}
// Goal check
if (current_state.size() == 1 && current_state[0].min_label == 1 && current_state[0].max_label == N) {
return current_g; // Found the optimal solution (due to admissible heuristic)
}
// Explore neighbors (moves)
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; }
// Create next state (grouping/merging - same logic as before)
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);
State next_state_unmerged;
for(auto& loc_pair : robots_by_location) { sort(loc_pair.second.begin(), loc_pair.second.end()); State merged = merge_robots_at_location(loc_pair.second); next_state_unmerged.insert(next_state_unmerged.end(), merged.begin(), merged.end()); }
State next_state = canonicalize(next_state_unmerged);
// Calculate costs for the next state
int next_g = current_g + 1;
int next_h = calculate_heuristic(next_state);
int next_f = next_g + next_h;
// Check if this state is new or we found a shorter path to it
auto it = g_costs.find(next_state);
if (it == g_costs.end() || next_g < it->second) {
g_costs[next_state] = next_g; // Update minimum cost
pq.push({next_f, next_g, next_state}); // Add to priority queue
}
}
}
}
return -1; // Goal not reachable
}
// --- Main Function (unchanged) ---
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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |