#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, w, h;
vector<string> grid;
int goal_mask;
// 4 hướng: up, down, left, right
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
// rotate: A = ccw, C = cw
int turn_ccw[4] = {2, 3, 1, 0}; // up->left(2), down->right(3), left->down(1), right->up(0)
int turn_cw [4] = {3, 2, 0, 1}; // up->right, down->left, left->up, right->down
struct Robot {
int mask, x, y;
bool operator<(Robot const& o) const {
if (mask!=o.mask) return mask<o.mask;
if (x!=o.x) return x<o.x;
return y<o.y;
}
};
// hash trạng thái thành string
string hash_state(vector<Robot>& A){
sort(A.begin(), A.end());
string s;
for(auto &r: A){
s += to_string(r.mask) + ":" + to_string(r.x) + "," + to_string(r.y) + ";";
}
return s;
}
int bfs(vector<Robot> start){
unordered_set<string> vis;
queue<pair<vector<Robot>,int>> q;
string h0 = hash_state(start);
vis.insert(h0);
q.push({start, 0});
while(!q.empty()){
auto [st, pushes] = q.front(); q.pop();
// kiểm tra đã hợp nhất hết?
if (st.size()==1 && st[0].mask == goal_mask)
return pushes;
// thử đẩy từng robot theo 4 hướng
for(int i=0; i<st.size(); i++){
for(int d=0; d<4; d++){
// sao chép trạng thái
vector<Robot> nxt = st;
Robot cur = nxt[i];
// đánh dấu robot i bị xoá tạm
nxt.erase(nxt.begin()+i);
int cx = cur.x, cy = cur.y, dir = d;
// di chuyển đến khi chạm vật cản
while(true){
int nx = cx + dx[dir], ny = cy + dy[dir];
// nếu ra ngoài hoặc gặp 'x' -> dừng
if (nx<0||nx>=h||ny<0||ny>=w|| grid[nx][ny]=='x') break;
cx = nx; cy = ny;
char c = grid[cx][cy];
if (c=='A') dir = turn_ccw[dir];
else if (c=='C') dir = turn_cw[dir];
}
// cur dừng ở (cx, cy)
cur.x = cx; cur.y = cy;
// hợp nhất với bất cứ robot nào cùng ô
bool merged = true;
while(merged){
merged = false;
for(int j=0; j<nxt.size(); j++){
if (nxt[j].x==cur.x && nxt[j].y==cur.y){
// hợp nhất
cur.mask |= nxt[j].mask;
nxt.erase(nxt.begin()+j);
merged = true;
break;
}
}
}
// thêm robot cur trở lại
nxt.push_back(cur);
// encode và kiểm tra visit
string hs = hash_state(nxt);
if (!vis.count(hs)){
vis.insert(hs);
q.push({nxt, pushes+1});
}
}
}
}
return -1;
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> w >> h;
grid.resize(h);
for(int i=0;i<h;i++) cin >> grid[i];
vector<Robot> start;
goal_mask = (1<<n) - 1;
// đọc vị trí robot
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
char c = grid[i][j];
if (c>='1' && c<='9'){
int id = c - '1'; // đánh số 0..n-1
start.push_back({1<<id, i, j});
// coi như ô trống để di chuyển qua
grid[i][j] = '.';
}
}
}
cout << bfs(start) << "\n";
return 0;
}
