#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <tuple> // For pairs or tuples if needed
using namespace std;
// Maximum dimensions and robot count based on constraints (n <= 9)
const int MAX_N = 9;
const int MAX_W = 50; // Assuming reasonable max dimensions
const int MAX_H = 50;
int N, W, H;
vector<string> grid;
// --- Robot Representation ---
struct Robot {
int min_label;
int max_label;
int r, c;
// Needed for sorting and using in maps/sets
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;
}
// Needed for comparison in maps/sets
bool operator==(const Robot& other) const {
return min_label == other.min_label &&
max_label == other.max_label &&
r == other.r &&
c == other.c;
}
};
// --- State Representation ---
// A state is defined by the set of robots currently existing.
// We use a vector sorted by min_label for canonical representation.
using State = vector<Robot>;
// --- Helper Functions ---
// Check if coordinates are within the grid boundaries
bool is_valid(int r, int c) {
return r >= 0 && r < H && c >= 0 && c < W;
}
// Get the character at a grid cell (handling boundary checks)
char get_grid_char(int r, int c) {
if (!is_valid(r, c)) {
return 'x'; // Treat outside as an obstacle/wall
}
return grid[r][c];
}
// --- Movement Simulation ---
// Directions: 0: Up (-1, 0), 1: Right (0, +1), 2: Down (+1, 0), 3: Left (0, -1)
int dr[] = {-1, 0, 1, 0};
int dc[] = {0, 1, 0, -1};
// Function to calculate the final position after a push
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; // Initial direction robot *intends* to move
// --- Rotation if starting on a plate ---
char start_plate = get_grid_char(r, c);
if (start_plate == 'A') { // Anti-clockwise
// Push Up(0) -> Left(3)
// Push Right(1) -> Up(0)
// Push Down(2) -> Right(1)
// Push Left(3) -> Down(2)
current_dir = (push_dir + 3) % 4;
} else if (start_plate == 'C') { // Clockwise
// Push Up(0) -> Right(1)
// Push Right(1) -> Down(2)
// Push Down(2) -> Left(3)
// Push Left(3) -> Up(0)
current_dir = (push_dir + 1) % 4;
}
// If not on a plate, current_dir remains push_dir
// --- Simulate movement step-by-step ---
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);
// Check for collision (wall or occlusion)
if (next_cell == 'x' || !is_valid(next_r, next_c)) {
break; // Stop at the current position (r, c)
}
// Move to the next cell
r = next_r;
c = next_c;
// --- Rotation if landing on a plate ---
if (next_cell == 'A') { // Anti-clockwise rotation of direction
// Moving Up(0) -> new dir Left(3)
// Moving Right(1) -> new dir Up(0)
// Moving Down(2) -> new dir Right(1)
// Moving Left(3) -> new dir Down(2)
current_dir = (current_dir + 3) % 4;
} else if (next_cell == 'C') { // Clockwise rotation of direction
// Moving Up(0) -> new dir Right(1)
// Moving Right(1) -> new dir Down(2)
// Moving Down(2) -> new dir Left(3)
// Moving Left(3) -> new dir Up(0)
current_dir = (current_dir + 1) % 4;
}
// If it's '.', numeric, or the initial location, direction doesn't change here
}
return {r, c}; // Return the final position
}
// --- Merging Logic ---
// Function to perform all possible merges at a given location
State merge_robots_at_location(const State& robots_at_loc) {
if (robots_at_loc.size() <= 1) {
return robots_at_loc; // No merging possible
}
State current_robots = robots_at_loc;
bool merged;
do {
merged = false;
State next_robots;
vector<bool> used(current_robots.size(), false);
// Sort to easily find adjacent ranges (optional but can help)
// sort(current_robots.begin(), current_robots.end()); // Already sorted by state canonicalization
for (int i = 0; i < current_robots.size(); ++i) {
if (used[i]) continue;
bool found_merge = false;
for (int j = i + 1; j < current_robots.size(); ++j) {
if (used[j]) continue;
// Check for compatibility (consecutive labels)
Robot r1 = current_robots[i];
Robot r2 = current_robots[j];
// Ensure they are at the same location (should be guaranteed by input)
if (r1.r != r2.r || r1.c != r2.c) continue;
if (r1.max_label + 1 == r2.min_label) {
// Merge r1 and r2
Robot merged_robot = {r1.min_label, r2.max_label, r1.r, r1.c};
next_robots.push_back(merged_robot);
used[i] = true;
used[j] = true;
merged = true;
found_merge = true;
break; // Merge r1 with the first compatible r2 found
} else if (r2.max_label + 1 == r1.min_label) {
// Merge r2 and r1
Robot merged_robot = {r2.min_label, r1.max_label, r1.r, r1.c};
next_robots.push_back(merged_robot);
used[i] = true;
used[j] = true;
merged = true;
found_merge = true;
break; // Merge r1 with the first compatible r2 found
}
}
// If robot i didn't merge with any other robot
if (!found_merge) {
// Only add if it wasn't marked used by merging with a previous robot
if(!used[i]) {
next_robots.push_back(current_robots[i]);
used[i] = true; // Mark as processed for this pass
}
}
}
// Update the list of robots for the next merging iteration
current_robots = next_robots;
sort(current_robots.begin(), current_robots.end()); // Keep sorted for consistency
} while (merged); // Repeat until no more merges occur in a pass
return current_robots;
}
// Canonicalize state by sorting robots
State canonicalize(State s) {
sort(s.begin(), s.end());
return s;
}
// --- Breadth-First Search (BFS) ---
int solve() {
// 1. Find initial state
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); // Canonicalize initial state
// 2. Initialize BFS
queue<State> q;
map<State, int> dist; // Map state to minimum pushes
q.push(initial_state);
dist[initial_state] = 0;
// 3. BFS loop
while (!q.empty()) {
State current_state = q.front();
q.pop();
int current_dist = dist[current_state];
// Check for goal state
if (current_state.size() == 1 && current_state[0].min_label == 1 && current_state[0].max_label == N) {
return current_dist; // Found the solution
}
// Explore possible moves (pushing each robot in 4 directions)
for (int i = 0; i < current_state.size(); ++i) { // Iterate through robots in current state
Robot robot_to_move = current_state[i];
for (int push_dir = 0; push_dir < 4; ++push_dir) { // Iterate through push directions
// Simulate the move
pair<int, int> final_pos = simulate_move(robot_to_move.r, robot_to_move.c, push_dir);
int final_r = final_pos.first;
int final_c = final_pos.second;
// Create the potential next state (before merging)
State next_state_unmerged = current_state;
next_state_unmerged[i].r = final_r;
next_state_unmerged[i].c = final_c;
// Group robots by location for merging
map<pair<int, int>, State> robots_by_location;
for(const auto& robot : next_state_unmerged) {
robots_by_location[{robot.r, robot.c}].push_back(robot);
}
// Perform merging at each location where merges might occur
State next_state_merged;
for(auto const& [pos, robots_at_pos] : robots_by_location) {
State merged_robots = merge_robots_at_location(robots_at_pos);
// Add the results of merging back to the overall state
next_state_merged.insert(next_state_merged.end(), merged_robots.begin(), merged_robots.end());
}
// Canonicalize the final state after merging
State final_next_state = canonicalize(next_state_merged);
// Check if this state has been visited
if (dist.find(final_next_state) == dist.end()) {
dist[final_next_state] = current_dist + 1;
q.push(final_next_state);
}
// If visited but found a shorter path (shouldn't happen in BFS, but good practice)
// else if (current_dist + 1 < dist[final_next_state]) {
// dist[final_next_state] = current_dist + 1;
// q.push(final_next_state); // Re-add with shorter distance (though BFS naturally finds shortest)
// }
}
}
}
// If the queue becomes empty and goal not reached
return -1;
}
// --- Main Function ---
int main() {
// Optimize C++ I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read input
cin >> N >> W >> H;
grid.resize(H);
for (int i = 0; i < H; ++i) {
cin >> grid[i];
}
// Solve the problem
int result = solve();
// Print output
cout << result << endl;
return 0;
}
