by_OctoberEstuary:

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
template <typename Tp>
void chmin(Tp &x, const Tp &y){ if(x > y) x = y; }
const int F[4]={0,-1,0,1};
const int G[4]={-1,0,1,0};

int n,m,k,ans=inf; char a[505][505];

int gx[4][505][505],gy[4][505][505],inq[4][505][505]; void work(int x, int y, int z){ if(gx[z][x][y] || gy[z][x][y]) return; if(x<1 || x>n || y<1 || y>m || a[x][y]=='x'){ gx[z][x][y] = gy[z][x][y] = -1; return; } if(inq[z][x][y]){ gx[z][x][y] = gy[z][x][y] = -2; return; } inq[z][x][y] = 1;

int u, v, w=z;
if(a[x][y] == 'A') (w += 3) &= 3;
if(a[x][y] == 'C') (w += 1) &= 3;
u = x + F[w]; v = y + G[w];

work(u, v, w);
gx[z][x][y] = gx[w][ u ][v]; gy[z][x][y] = gy[w][ u ][v];
if(gx[z][x][y] == -1){
	gx[z][x][y] = x; gy[z][x][y] = y;
}
inq[z][x][y] = 0;
return;

}

int f[10][10][505][505],L,R; pair<int,int> qa[250005]; priority_queue<pair<int,pair<int,int> > > qb; int vis[505][505],ql,qr; bool cmp(pair<int,int> x, pair<int,int> y){ return f[L][R][x.first][x.second] < f[L][R][y.first][y.second]; } void dij(){ int l=L, r=R; memset(vis, 0, sizeof(vis)); ql=1; qr=0; for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(f[l][r][i][j] < inf){ qa[++qr] = make_pair(i,j); } stable_sort(qa+1, qa+qr+1, cmp); int x,y,u,v; while(!qb.empty() || ql<=qr){ if(ql<=qr && qb.empty()){ tie(x,y) = qa[ql++]; } else if(ql>qr && !qb.empty()){ tie(x,y) = qb.top().second; qb.pop(); } else if(cmp(qa[ql], qb.top().second)){ tie(x,y) = qa[ql++]; } else { tie(x,y) = qb.top().second; qb.pop(); }

	if(vis[x][y]) continue;
	vis[x][y] = 1;
	
	for(int i=0; i<4; i++)if(gx[i][x][y] > 0){
		u = gx[i][x][y];
		v = gy[i][x][y];
		if(f[l][r][ u ][v] > f[l][r][x][y] + 1){
			f[l][r][ u ][v] = f[l][r][x][y] + 1;
			qb.emplace(-f[l][r][ u ][v], make_pair(u,v));
		}
	}
}

}

int main(){ scanf("%d%d%d",&k,&m,&n); for(int i=1; i<=n; i++) scanf("%s",a[i]+1);

for(int i=1; i<=n; i++)for(int j=1; j<=m; j++){
	work(i, j, 0);
	work(i, j, 1);
	work(i, j, 2);
	work(i, j, 3);
}

memset(f, 0x3f, sizeof(f));
for(int i=1; i<=n; i++)for(int j=1; j<=m; j++)if(isdigit(a[i][j])){
	f[a[i][j]-'0'][a[i][j]-'0'][i][j] = 0;
}

for(int i=1; i<=k; i++){
	for(int l=1,r=i; r<=k; l++,r++){
		for(int d=l; d<r; d++){
			for(int u=1; u<=n; u++)for(int v=1; v<=m; v++){
				chmin(f[l][r][ u ][v], f[l][d][ u ][v] + f[d+1][r][ u ][v]);
			}
		}
		L=l; R=r;
		dij();
	}
}

for(int i=1; i<=n; i++)for(int j=1; j<=m; j++) chmin(ans, f[1][k][i][j]);
(ans==inf) ? printf("-1") : printf("%d",ans);
return 0;

} /* 0: L 1: U 2: R 3: D */</pre>