#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9; // Infinity
const int MAX_N = 9; // Maximum number of robots
const int MAX_V = 500 * 500; // Maximum number of reachable grids
int w, h, n; // Width, height, and number of robots
vector<string> grid;
vector<pair<int, int>> robot_positions;
vector<int> reachable_cells; // List of reachable grid IDs
unordered_map<int, int> cell_to_index; // Map grid ID to compressed index
vector<vector<int>> dist; // Distances between reachable cells
// Convert 2D coordinates to a single grid ID
inline int get_id(int x, int y) {
return x * w + y;
}
// Precompute reachable cells and distances
void preprocess() {
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
queue<pair<int, int>> q;
vector<vector<bool>> visited(h, vector<bool>(w, false));
// Start BFS from all robot positions
for (auto [x, y] : robot_positions) {
q.push({x, y});
visited[x][y] = true;
}
// BFS for reachable cells
while (!q.empty()) {
auto [cx, cy] = q.front();
q.pop();
int cell_id = get_id(cx, cy);
reachable_cells.push_back(cell_id);
cell_to_index[cell_id] = (int)reachable_cells.size() - 1;
for (int d = 0; d < 4; ++d) {
int nx = cx, ny = cy;
while (true) {
int tx = nx + dx[d], ty = ny + dy[d];
if (tx < 0 || tx >= h || ty < 0 || ty >= w || grid[tx][ty] == 'x') break;
nx = tx;
ny = ty;
// Rotate if on a plate
if (grid[nx][ny] == 'A') {
tie(dx[d], dy[d]) = make_pair(-dy[d], dx[d]);
} else if (grid[nx][ny] == 'C') {
tie(dx[d], dy[d]) = make_pair(dy[d], -dx[d]);
}
}
if (!visited[nx][ny]) {
visited[nx][ny] = true;
q.push({nx, ny});
}
}
}
// Compute pairwise distances between reachable cells
int V = reachable_cells.size();
dist.assign(V, vector<int>(V, INF));
for (int i = 0; i < V; ++i) {
queue<int> q;
vector<int> d(V, INF);
d[i] = 0;
q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
int x = reachable_cells[u] / w, y = reachable_cells[u] % w;
for (int d = 0; d < 4; ++d) {
int nx = x, ny = y;
while (true) {
int tx = nx + dx[d], ty = ny + dy[d];
if (tx < 0 || tx >= h || ty < 0 || ty >= w || grid[tx][ty] == 'x') break;
nx = tx;
ny = ty;
}
int v = cell_to_index[get_id(nx, ny)];
if (d[v] > d[u] + 1) {
d[v] = d[u] + 1;
q.push(v);
}
}
}
// Store distances
for (int j = 0; j < V; ++j) {
dist[i][j] = d[j];
}
}
}
// Solve using DP with bitmask
int solve() {
int V = reachable_cells.size();
vector<vector<int>> dp(1 << n, vector<int>(V, INF));
// Initialize DP for single robots
for (int i = 0; i < n; ++i) {
int start = cell_to_index[get_id(robot_positions[i].first, robot_positions[i].second)];
dp[1 << i][start] = 0;
}
// Iterate over all subsets of robots
for (int mask = 1; mask < (1 << n); ++mask) {
for (int u = 0; u < V; ++u) {
if (dp[mask][u] == INF) continue;
// Try merging with other subsets
for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
int rest = mask ^ submask;
for (int v = 0; v < V; ++v) {
dp[mask][v] = min(dp[mask][v], dp[submask][u] + dp[rest][v] + dist[u][v]);
}
}
}
}
// Find the minimum cost to merge all robots
int result = INF;
for (int u = 0; u < V; ++u) {
result = min(result, dp[(1 << n) - 1][u]);
}
return result == INF ? -1 : result;
}
int main() {
cin >> n >> w >> h;
grid.resize(h);
for (int i = 0; i < h; ++i) {
cin >> grid[i];
}
// Parse robot positions
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
if (isdigit(grid[i][j])) {
robot_positions.push_back({i, j});
}
}
}
preprocess();
cout << solve() << endl;
return 0;
}
