//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 * 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) {
if (thuoc[i][j]) return;
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[10][10], k;
ll d[500 * 500 + 1][46];
bool vis[500 * 500 + 1][46];
pii ptich[50];
vector<pii> p[N * N];
void dij() {
queue<pii> q;
for (int i = 1; i <= cur; i ++) {
for (int j = 1; j <= k; j ++) {
d[i][j] = inf;
}
}
for (int i = 1; i <= n; i ++) {
q.push({idx[bdau[i].fi][bdau[i].se], ax[i][i]});
vis[idx[bdau[i].fi][bdau[i].se]][ax[i][i]] = 1;
d[idx[bdau[i].fi][bdau[i].se]][ax[i][i]] = 0;
}
// lam tung len
for (int len = 1; len <= n; len ++) {
//cout << "len " << len << " " << q.size() << endl;
if (len == 1) {
while (q.size()) {
auto u = q.front();
q.pop();
//cout << " " << d[u.fi][u.se] << " xy " << dinh[u.fi].fi << " " << dinh[u.fi].se << " | " << ptich[u.se].fi << " " << ptich[u.se].se << endl;
for (auto v : adj[u.fi]) {
if (d[v][u.se] > d[u.fi][u.se] + 1) {
d[v][u.se] = d[u.fi][u.se] + 1;
q.push({v, u.se});
}
}
}
continue;
}
ll mn = inf;
for (int u = 1; u <= cur; u ++) {
for (int i = 1; i <= n; i ++) {
ll j = i + len - 1;
if (j > n) break;
for (int mid = i; mid < j; mid ++) {
d[u][ax[i][j]] = min(d[u][ax[i][j]], d[u][ax[i][mid]] + d[u][ax[mid + 1][j]]);
}
mn = min(mn, d[u][ax[i][j]]);
if (d[u][ax[i][j]] != inf) {
p[d[u][ax[i][j]]].push_back({u, ax[i][j]});
//cout << " push " << d[u][ax[i][j]] << " | " << dinh[u].fi << " " << dinh[u].se << " | " << i << " " << j << endl;
}
}
}
if (mn == inf) {
//cout << " cut" << endl;
continue;
}
for (auto it : p[mn]) {
q.push(it);
vis[it.fi][it.se] = 1;
}
while (q.size()) {
auto u = q.front();
q.pop();
//cout << " " << d[u.fi][u.se] << " xy " << dinh[u.fi].fi << " " << dinh[u.fi].se << " | " << ptich[u.se].fi << " " << ptich[u.se].se << endl;
ll c = d[u.fi][u.se];
for (auto it : p[c + 1]) {
if (d[it.fi][it.se] < c + 1) continue;
q.push({it.fi, it.se});
}
p[c + 1].clear();
for (auto v : adj[u.fi]) {
if (d[v][u.se] > c + 1) {
d[v][u.se] = c + 1;
q.push({v, u.se});
vis[v][u.se] = 1;
}
}
}
}
}
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);
}
for (int i = 1; i <= n; i ++) {
for (int j = i; j <= n; j ++) {
ax[i][j] = ++ k;
ptich[k] = {i, j};
}
}
dij();
for (int u = 1; u <= cur; u ++) {
ans = min(ans, d[u][ax[1][n]]);
}
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;
}
