#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#include <tuple> // For std::tie used in comparison
#include <vector>
#include <algorithm> // For std::sort
#include <cctype> // For std::isdigit
using namespace std;
// Struct to represent a robot (original or composite)
struct Robot {
int min_l, max_l; // Min and max labels of merged robots
int r, c; // Row and column position
// Comparison operator for sorting and using in std::set/map.
bool operator<(const Robot& other) const {
return tie(min_l, max_l, r, c) < tie(other.min_l, other.max_l, other.r, other.c);
}
bool operator==(const Robot& other) const {
return tie(min_l, max_l, r, c) == tie(other.min_l, other.max_l, other.r, other.c);
}
};
// --- Constants and Global Variables ---
const int MAX_H = 501; // Max dimensions + 1 for safety
const int MAX_W = 501;
int N; // Number of initial robots
int W; // Grid width
int H; // Grid height
vector<string> grid; // Grid layout ('x', '.', 'A', 'C')
vector<pair<int, int>> initial_pos; // Store initial positions for robots 1 to N
// 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};
// --- Precomputation Data Structure ---
pair<int, int> precomputed_moves[MAX_H][MAX_W][4];
// Function to check if a cell is valid (within bounds and not an obstacle)
bool isValid(int r, int c) {
return r >= 0 && r < H && c >= 0 && c < W && grid[r][c] != 'x';
}
// --- Precomputation Function (Revised Simulation Logic) ---
void precompute_all_moves() {
for (int r = 0; r < H; ++r) {
for (int c = 0; c < W; ++c) {
// Cannot start move from an obstacle
if (grid[r][c] == 'x') {
for (int start_dir = 0; start_dir < 4; ++start_dir) precomputed_moves[r][c][start_dir] = {-1, -1};
continue;
}
// Precompute for each of the 4 initial push directions
for (int start_dir = 0; start_dir < 4; ++start_dir) {
int nr = r, nc = c; // Current position, initialized to start
int current_dir = start_dir; // Effective direction of travel, initialized
// --- Determine Initial Move Direction (Revised Rule 2) ---
bool starting_on_rotator = (grid[r][c] == 'A' || grid[r][c] == 'C');
int first_step_dir = start_dir; // Default to original push direction
if (starting_on_rotator) {
int rotated_dir = (grid[r][c] == 'A') ? (start_dir + 3) % 4 : (start_dir + 1) % 4;
int rotated_next_r = r + dr[rotated_dir];
int rotated_next_c = c + dc[rotated_dir];
// Prefer rotated direction if the first step is valid
if (isValid(rotated_next_r, rotated_next_c)) {
first_step_dir = rotated_dir;
}
// else: keep original push direction (first_step_dir = start_dir)
// Validity of original direction step checked below.
}
// Check if the first step (in the determined first_step_dir) is valid
int first_step_r = r + dr[first_step_dir];
int first_step_c = c + dc[first_step_dir];
if (!isValid(first_step_r, first_step_c)) {
// Cannot even take the first step, robot stays at (r, c)
precomputed_moves[r][c][start_dir] = {r, c};
continue; // Next start_dir
}
// --- Take the First Step ---
nr = first_step_r;
nc = first_step_c;
current_dir = first_step_dir; // Update effective direction
// --- Continue Simulation Loop (Rule 1 applies from now on) ---
while (true) {
// Check for rotation plate at the *current* cell (nr, nc) - Rule 1
// This updates the direction for the *next* move.
if (grid[nr][nc] == 'A') {
current_dir = (current_dir + 3) % 4;
} else if (grid[nr][nc] == 'C') {
current_dir = (current_dir + 1) % 4;
}
// Calculate next potential cell based on current_dir
int next_r = nr + dr[current_dir];
int next_c = nc + dc[current_dir];
// Check if the next step is valid
if (!isValid(next_r, next_c)) {
break; // Blocked, stop at current position (nr, nc)
}
// Move to the next cell
nr = next_r;
nc = next_c;
// Loop continues, will check grid[nr][nc] for rotation next iteration
}
// Store the final resting position
precomputed_moves[r][c][start_dir] = {nr, nc};
}
}
}
}
// --- Optimized simulate_move using precomputation ---
pair<int, int> simulate_move(int r, int c, int dir) {
return precomputed_moves[r][c][dir];
}
// Function to perform all possible merges iteratively on the current set of robots.
void perform_merges(vector<Robot>& current_robots) {
if (current_robots.size() < 2) return;
bool merged_in_pass = true;
while (merged_in_pass) {
merged_in_pass = false;
vector<Robot> next_round_robots;
vector<bool> processed(current_robots.size(), false);
sort(current_robots.begin(), current_robots.end(), [](const Robot& a, const Robot& b){
return tie(a.r, a.c, a.min_l, a.max_l) < tie(b.r, b.c, b.min_l, b.max_l);
});
for (int i = 0; i < current_robots.size(); ++i) {
if (processed[i]) continue;
bool merged_robot_i = false;
for (int j = i + 1; j < current_robots.size(); ++j) {
if (processed[j]) continue;
if (current_robots[i].r != current_robots[j].r || current_robots[i].c != current_robots[j].c) break;
if (current_robots[i].max_l + 1 == current_robots[j].min_l || current_robots[j].max_l + 1 == current_robots[i].min_l) {
Robot merged_robot;
merged_robot.min_l = min(current_robots[i].min_l, current_robots[j].min_l);
merged_robot.max_l = max(current_robots[i].max_l, current_robots[j].max_l);
merged_robot.r = current_robots[i].r;
merged_robot.c = current_robots[i].c;
next_round_robots.push_back(merged_robot);
processed[i] = true; processed[j] = true;
merged_in_pass = true; merged_robot_i = true;
break;
}
}
if (!processed[i]) {
next_round_robots.push_back(current_robots[i]);
processed[i] = true;
}
}
current_robots = next_round_robots;
if (current_robots.size() < 2) break;
}
sort(current_robots.begin(), current_robots.end());
}
// Solves the problem using BFS with precomputed moves
int solve() {
vector<Robot> initial_state;
for (int i = 0; i < N; ++i) {
initial_state.push_back({i + 1, i + 1, initial_pos[i].first, initial_pos[i].second});
}
perform_merges(initial_state);
queue<pair<vector<Robot>, int>> q;
set<vector<Robot>> visited;
q.push({initial_state, 0});
visited.insert(initial_state);
while (!q.empty()) {
vector<Robot> current_robots = q.front().first;
int current_pushes = q.front().second;
q.pop();
if (current_robots.size() == 1 && current_robots[0].min_l == 1 && current_robots[0].max_l == N) {
return current_pushes;
}
for (int i = 0; i < current_robots.size(); ++i) {
for (int dir_idx = 0; dir_idx < 4; ++dir_idx) {
vector<Robot> next_robots = current_robots;
Robot moving_robot = next_robots[i];
pair<int, int> final_pos = simulate_move(moving_robot.r, moving_robot.c, dir_idx);
// Check if the starting position itself was invalid (e.g., 'x')
// simulate_move would return {-1, -1} based on precomputation
if (final_pos.first == -1) continue;
next_robots[i].r = final_pos.first;
next_robots[i].c = final_pos.second;
perform_merges(next_robots);
if (visited.find(next_robots) == visited.end()) {
visited.insert(next_robots);
q.push({next_robots, current_pushes + 1});
}
}
}
}
return -1;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N >> W >> H;
grid.resize(H);
initial_pos.resize(N);
vector<bool> pos_found(N, false);
for (int i = 0; i < H; ++i) {
cin >> grid[i];
for (int j = 0; j < W; ++j) {
if (isdigit(grid[i][j])) {
int robot_label = grid[i][j] - '0';
int robot_id = robot_label - 1;
if (robot_id >= 0 && robot_id < N) {
initial_pos[robot_id] = {i, j};
pos_found[robot_id] = true;
grid[i][j] = '.';
} else {
// Silently ignore invalid digits, treat as '.'
grid[i][j] = '.';
}
}
}
}
bool all_found = true;
for(int i=0; i<N; ++i) {
if (!pos_found[i]) {
all_found = false;
cerr << "Error: Robot " << (i+1) << " not found on the initial grid." << endl;
return 1;
}
}
// Call precomputation function before solving
precompute_all_moves();
// Call the solver function and print the result
cout << solve() << endl;
return 0;
}
