//Huyduocdithitp
#include<bits/stdc++.h>
typedef int ll;
#define endl '\n'
#define fi first
#define se second
#define pii pair<ll, ll>
#define N 505
using namespace std;
ll getbit(ll mask, ll i) {
return (mask >> i) & 1;
}
ll onbit(ll mask, ll i){
return mask | (1 << i);
}
const ll inf = 1e9;
const ll hx[] = {-1, 0, 1, 0}; // len phai xuong trai
const ll hy[] = {0, 1, 0, -1};
bool ghuy4g;
ll n, w, h, ans = inf;
char a[N][N];
bool is[N][N][4];
ll vst[N][N][4];
pii nxt[N][N][4];
vector<ll> adj[N];
ll luot = 0;
bool isthem[N][N];
queue<pii> q;
pii dfs(ll i, ll j, ll t) {
////cout << i << " " << j << " " << t << endl;
vst[i][j][t] = luot;
ll ii, jj, tt;
if (a[i][j] == 'A') {
tt = t - 1;
if (tt < 0) tt = 3;
ii = i + hx[tt];
jj = j + hy[tt];
}
else if (a[i][j] == 'C') {
tt = t + 1;
if (tt == 4) tt = 0;
ii = i + hx[tt];
jj = j + hy[tt];
}
else {
ii = i + hx[t];
jj = j + hy[t];
tt = t;
}
if (ii < 1 || ii > h || jj < 1 || jj > w || a[ii][jj] == 'x') {
////cout << "chan roi " << endl;
if (isthem[i][j] == 0){
isthem[i][j] = 1;
q.push({i, j});
}
return nxt[i][j][t] = {i, j};
}
if (vst[ii][jj][tt] == luot) {
return nxt[i][j][t] = {-1, -1};
}
else if (vst[ii][jj][tt] > 0 && vst[ii][jj][tt] != luot) {
return nxt[i][j][t] = dfs(ii, jj, tt);
}
else {
return nxt[i][j][t] = dfs(ii, jj, tt);
}
vst[i][j][t] = luot;
}
pii bdau[10];
ll idx[N][N]; // idx cua dinh i j
pii dinh[N * N];
ll cur = 0;
bool thuoc[N][N];
void dfs2(ll i, ll j) {
cur ++ ;
idx[i][j] = cur;
dinh[cur] = {i, j};
thuoc[i][j] = 1;
for (int z = 0; z < 4; z ++) {
pii moi = nxt[i][j][z];
if (moi.fi != 0 && moi.fi != -1) {
if (thuoc[moi.fi][moi.se] == 0) {
dfs2(moi.fi, moi.se);
}
}
if (moi.fi != i || moi.se != j) {
adj[idx[i][j]].push_back({idx[moi.fi][moi.se]});
}
}
}
ll ax[N]; // ax[mask] la mask 000101..1001 co chi so la bao nhieu
ll ax1[N]; // ax[k] = mask
ll k;
ll check(ll mask1, ll mask2) {
ll mask = (mask1 & mask2);
if (mask != 0) { // co bit chung
return 0;
}
mask = (mask1 ^ mask2);
bool flag = 1;
ll sd = 0;
for (int i = 1; i <= n; i ++) {
if (getbit(mask, i - 1) == 0) continue;
ll j = i;
while (j <= n && getbit(mask, j - 1) == 1) {
j ++ ;
}
i = j - 1;
sd ++ ;
}
if (sd > 1) {
flag = 0;
}
if (flag == 0) return 0;
return ax[mask];
}
void dij() {
vector<vector<ll>> d(cur + 1, vector<ll>(k + 1));
for (int i = 1; i <= cur; i ++) {
for (int j = 1; j <= k; j ++) {
d[i][j] = inf;
}
}
priority_queue<pair<ll, pii>, vector<pair<ll, pii>>, greater<pair<ll, pii>>> pq;
for (int i = 1; i <= n; i ++) {
ll x = bdau[i].fi, y = bdau[i].se, mask = onbit(0, i - 1), id = ax[mask];
ll u = idx[x][y];
d[u][id] = 0;
pq.push({d[u][id], {u, id}});
}
while (pq.size()) {
auto c = pq.top().fi;
auto u = pq.top().se;
pq.pop();
if (c > d[u.fi][u.se]) continue;
//cout << endl;
if (__builtin_popcount(ax1[u.se]) == n) {
ans = min(ans, c);
}
ll mask = ax1[u.se];
for (int i = 1; i <= k; i ++) {
if (i == u.se) continue;
if (d[u.fi][i] == inf) continue;
ll mask2 = ax1[i];
ll newid = check(mask, mask2);
if (newid > 0 && d[u.fi][newid] > d[u.fi][u.se] + d[u.fi][i]) {
d[u.fi][newid] = d[u.fi][u.se] + d[u.fi][i];
pq.push({d[u.fi][newid], {u.fi, newid}});
}
}
for (auto v : adj[u.fi]) {
if (d[v][u.se] > c + 1) {
d[v][u.se] = c + 1;
pq.push({d[v][u.se], {v, u.se}});
}
}
}
}
void pre() {
/*for (int i = 1; i <= n; i ++) {
for (int z = 0; z < 4; z ++) {
++ luot;
dfs(bdau[i].fi, bdau[i].se, z);
}
}*/
for (int i = 1; i <= n; i ++) {
q.push({bdau[i].fi, bdau[i].se});
}
while (q.size()) {
auto u = q.front();
q.pop();
for (int z = 0; z < 4; z ++) {
if (vst[u.fi][u.se][z] > 0) continue;
++ luot;
dfs(u.fi, u.se, z);
}
}
////cout << nxt[1][1][0].fi << " " << nxt[1][1][0].se << endl;;
////cout << nxt[1][1][1].fi << " " << nxt[1][1][1].se << endl;;
////cout << nxt[1][1][2].fi << " " << nxt[1][1][2].se << endl;;
for (int i = 1; i <= n; i ++) {
dfs2(bdau[i].fi, bdau[i].se);
}
//cout << "cur " << cur << endl;
//cout << nxt[5][5][1].fi << " " << nxt[5][5][1].se << endl;
for (int mask = 0; mask < (1 << n); mask ++) {
bool flag = 1;
ll sd = 0;
for (int i = 1; i <= n; i ++) {
if (getbit(mask, i - 1) == 0) continue;
ll j = i;
while (j <= n && getbit(mask, j - 1) == 1) {
j ++ ;
}
i = j - 1;
sd ++ ;
}
if (sd > 1) {
flag = 0;
}
if (flag) {
k ++ ;
ax[mask] = k;
ax1[k] = mask;
}
}
dij();
if (ans == inf) {
cout << -1;
}
else {
cout << ans;
}
}
bool klinh;
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> w >> h;
for (int i = 1; i <= h; i ++) {
for (int j = 1; j <= w; j ++) {
cin >> a[i][j];
if ('1' <= a[i][j] && a[i][j] <= '9') {
bdau[a[i][j] - '0'] = {i, j};
}
}
}
pre();
cerr << fabs(&klinh - &ghuy4g) / double(1024 * 1024);
return 0;
}
