#include<bits/stdc++.h>
using namespace std;
// PES 2021 - abril. "Bacterias alienigenas" (60 pts: DFS + Busqueda priorizada sobre estado ampliado usando multiples colas en vez de cola priorizada)
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define lli long long int
#define vi vector<int>
#define vlli vector<long long int>
#define pii pair<int, int>
#define plli pair<lli, lli>
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define repa(i, a, b) for(int i = (a); i >= (b); i--)
#define repv(x, v) for(auto x : v)
#define debug(x) cout << #x << " = " << x << endl
#define debugsl(x) cout << #x << " = " << x << ", "
#define debugarr(x, a, b) cout << #x << " = ["; rep(i, a, b) cout << x[i] << ", "; cout << "]\n"
#define pb push_back
#define nl "\n"
#define MAX_N 503
#define MAX_BACTERIA 10
#define CICLADO 1000
#define norte 0
#define este 1
#define sur 2
#define oeste 3
#define invalido 0
#define valido 1
#define rotahorario 2
#define rotaantihorario 3
#define fila first
#define columna second
#define inicio first.first
#define fin first.second
#define cfila second.first
#define ccolumna second.second
#define horario(x) ((x + 1) & 3)
#define antihorario(x) ((x + 3) & 3)
#define une(a, b, c, d) ((a << 24) | (b << 20) | (c << 10) | d)
#define binicio(x) (x >> 24)
#define bfin(x) ((x >> 20) & 0xF)
#define cfila(x) ((x >> 10) & 0x3FF)
#define ccolumna(x) (x & 0x3FF)
int n, filas, columnas, mapa[MAX_N][MAX_N], res, tmp, maximo, cnt;
int dist[MAX_BACTERIA][MAX_BACTERIA][MAX_N][MAX_N];
pii destino[4][MAX_N][MAX_N], bact[MAX_BACTERIA], delta[4] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}, coorddest;
int actual;
string s;
pii dfs(int fil, int col, int dir){
if (destino[dir][fil][col].fila) return destino[dir][fil][col]; // SI YA CONOCE EL RESULTADO, DEVUELVELO
if (mapa[fil][col] == invalido) return {fil, col}; // SI ES UNA POSICION INVALIDA DEVUELVELA
int dirorig = dir;
if (mapa[fil][col] == rotahorario) dir = horario(dir);
else if (mapa[fil][col] == rotaantihorario) dir = antihorario(dir);
if (mapa[fil + delta[dir].fila][col + delta[dir].columna] == invalido) return {fil, col};
destino[dirorig][fil][col] = {CICLADO, CICLADO};
return destino[dirorig][fil][col] = dfs(fil + delta[dir].fila, col + delta[dir].columna, dir);
}
int main()
{
fastio;
cin >> n >> columnas >> filas;
// LEE EL MAPA
rep(fil, 1, filas){
cin >> s;
rep(col, 1, columnas){
if (s[col - 1] == '.') mapa[fil][col] = valido;
else if (s[col - 1] == 'x') mapa[fil][col] = invalido;
else if (s[col - 1] == 'A') mapa[fil][col] = rotaantihorario;
else if (s[col - 1] == 'C') mapa[fil][col] = rotahorario;
else{
mapa[fil][col] = valido;
bact[s[col - 1] - '0'].fila = fil;
bact[s[col - 1] - '0'].columna = col;
}
}
}
// CALCULA A DONDE LLEGA UN ROBOT QUE SEA EMPUJADO EN CADA UNA DE LAS 4 DIRECCIONES DESDE CADA PUNTO POSIBLE DE ORIGEN.
rep(fil, 1, filas){
rep(col, 1, columnas){
rep(dir, norte, oeste){
destino[dir][fil][col] = dfs(fil, col, dir);
}
}
}
// HAZ UNA BUSQUEDA USANDO UNA COLA PRIORIZADA, EL ESTADO ES LA COORDENADA MAS LA ETIQUETA DE LA BACTERIA
// LAS TRANSICIONES SON
// LAS 4 DIRECCIONES EN QUE SE PUEDE EMPUJAR
// LAS ETIQUETAS CON LAS QUE SE PUEDE UNIR
// LOS ESTADOS VALIDOS SON AQUELLOS QUE REDUZCAN EL MEJOR CAMINO ENCONTRADO
maximo = filas * columnas + 1;
rep(fil, 1, filas) rep(col, 1, columnas) rep(b1, 1, n) rep(b2, b1, n) dist[b1][b2][fil][col] = maximo;
vector<vector<int> > q(maximo);
rep(b, 1, n){
q[0].pb(une(b, b, bact[b].fila, bact[b].columna)); // INICIALMENTE AGREGA A LA COLA TODAS LAS BACTERIAS SOLAS CON SU POSICION
dist[b][b][bact[b].fila][bact[b].columna] = 0;
}
cnt = 0;
while (cnt < maximo){
while (q[cnt].size()){
actual = q[cnt].back();
q[cnt].pop_back();
// UNICAMENTE PROCESALO SI NADIE LO HA MEJORADO
if (dist[binicio(actual)][bfin(actual)][cfila(actual)][ccolumna(actual)] == cnt){
// HAZ TRANSICIONES DE EMPUJAR LA BACTERIA QUE SE TIENE EN LAS 4 DIRECCIONES
rep(dir, norte, oeste){
coorddest = destino[dir][cfila(actual)][ccolumna(actual)];
if (dist[binicio(actual)][bfin(actual)][coorddest.fila][coorddest.columna] > cnt + 1){
q[cnt + 1].pb(une(binicio(actual), bfin(actual), coorddest.fila, coorddest.columna));
dist[binicio(actual)][bfin(actual)][coorddest.fila][coorddest.columna] = cnt + 1;
}
}
// TRANSICIONES QUE UNEN BACTERIAS
rep(b, bfin(actual) + 1, n){ // VE SI PUEDES UNIR CON BACTERIAS CON ETIQUETAS "MAYORES"
tmp = dist[bfin(actual) + 1][b][cfila(actual)][ccolumna(actual)]; // FIJATE SI YA PUDO LLEGAR A ESA CASILLA CON LA ETIQUETA QUE BUSCAS
if (tmp < maximo && (tmp + cnt) < maximo && tmp + cnt < dist[binicio(actual)][b][cfila(actual)][ccolumna(actual)]){
q[tmp + cnt].pb(une(binicio(actual), b, cfila(actual), ccolumna(actual)));
dist[binicio(actual)][b][cfila(actual)][ccolumna(actual)] = tmp + cnt;
}
}
repa(b, binicio(actual) - 1, 1){ // VE SI PUEDES UNIRTE CON ETIQUETAS "MENORES"
tmp = dist[b][binicio(actual) - 1][cfila(actual)][ccolumna(actual)]; // FIJATE SI YA PUDO LLEGAR A ESA CASILLA CON LA ETIQUETA QUE BUSCAS
if (tmp < maximo && (tmp + cnt) < maximo && tmp + cnt < dist[b][bfin(actual)][cfila(actual)][ccolumna(actual)]){
q[tmp + cnt].pb(une(b, bfin(actual), cfila(actual), ccolumna(actual)));
dist[b][bfin(actual)][cfila(actual)][ccolumna(actual)] = tmp + cnt;
}
}
}
}
q[cnt].clear(); // ES NECESARIO LIMPIAR LA COLA PARA QUE NO SE QUEDE OCUPANDO MEMORIA.
while (cnt < maximo && !q[cnt].size()) ++cnt;
}
res = maximo;
rep(fil, 1, filas)
rep(col, 1, columnas)
res = min(res, dist[1][n][fil][col]);
if (res == maximo) res = -1;
cout << res;
return 0;
}
