// 2
#ifndef LOCAL
#define NDEBUG 1
#endif
#include<bits/stdc++.h>
int numRobot, numRow, numCol;
std::vector<std::vector<char>> data;
struct Pos{
int row, col;
int index() const{
assert((unsigned) row<(unsigned) numRow); assert((unsigned) col<(unsigned) numCol);
return col+numCol*row;
}
};
struct State{
int dir; // dir+1: clockwise
int row, col;
std::pair<int, int> dirVector() const{
std::pair<int, int> result{1, 0};
switch(dir){
case 3: result={result.second,-result.first};
case 2: result={result.second,-result.first};
case 1: result={result.second,-result.first};
case 0: return result;
}
assert(false);
}
int index() const{return dir+4*Pos{row, col}.index();}
};
int const loop=-2, uncomputed=-1;
std::vector<int> memory;
int compute(State it){
auto& curMemory=memory[it.index()];
if(curMemory!=uncomputed) return curMemory;
State next=it;
switch(data[next.row][next.col]){
case 'A':
next.dir=(next.dir-1)&3; break;
case 'C':
next.dir=(next.dir+1)&3; break;
case 'x':
assert(false); __builtin_unreachable();
}
next.row+=next.dirVector().first; next.col+=next.dirVector().second;
if((unsigned)next.row>=(unsigned)numRow or (unsigned)next.col>=(unsigned)numCol or
data[next.row][next.col]=='x')
return curMemory=Pos{it.row, it.col}.index();
curMemory=loop;
return curMemory=compute(next);
}
int getMemory(int pos, int dir){
int result=memory[dir+4*pos];
assert(result!=uncomputed);
return result;
}
int main(){
std::ios::sync_with_stdio(0);std::cin.tie(0);
std::cin>>numRobot>>numCol>>numRow;
if(numRobot==1){std::cout<<"0\n"; return 0;}
data.resize(numRow);
for(auto& row: data){
row.resize(numCol+1);
std::cin>>row.data();
assert(row.back()==0); row.pop_back();
assert(row.back()!=0);
}
memory.assign(numRow*numCol*4, uncomputed);
for(int row=0; row<numRow; ++row)
for(int col=0; col<numCol; ++col)
if(data[row][col]!='x')
for(int dir=0; dir<4; ++dir){
auto const result=compute({dir, row, col});
(void) result;
/*
std::cerr<<row<<' '<<col<<' '<<dir<<'-'
<<result/numCol<<' '<<result%numCol<<'\n';
*/
}
int const numPos=numRow*numCol;
std::vector<int> distance_(numPos*numRobot*numRobot, INT_MAX);
auto const distance=[&](int a, int b, int pos)->int&{
assert(0<=a); assert(a<=b); assert(b<numRobot);
assert((unsigned)pos<unsigned(numPos));
return distance_[a+numRobot*(b+numRobot*pos)];
};
struct State{
char a, b; int pos;
};
std::vector<std::vector<State>> queue(numPos);
auto const update=[&](int curDistance, int a, int b, int pos){
if(curDistance<distance(a, b, pos)){
while(curDistance>=(int)queue.size()) queue.resize(queue.size()*2);
queue[distance(a, b, pos)=curDistance].push_back({(char) a, (char) b, pos});
}
};
int result=INT_MAX;
for(int a=numRobot; a--;){
for(int row=0; row<numRow; ++row)
for(int col=0; col<numCol; ++col){
assert(distance(a, a, Pos{row, col}.index())==INT_MAX);
if(data[row][col]==char('1'+a)){
auto const pos=Pos{row, col}.index();
update(0, a, a, pos);
}
}
}
for(int curDistance=0; curDistance<(int)queue.size(); ++curDistance){
for(int index=0; index<(int)queue[curDistance].size(); ++index){
auto [a, b, pos]=queue[curDistance][index];
if(curDistance!=distance(a, b, pos)) continue;
if(a==0 and b==numRobot-1){
result=std::min(result, curDistance);
continue;
}
for(int c=b+1; c<numRobot;++c){
if(auto const d1=distance(b+1, c, pos); d1<=curDistance)
update(curDistance+d1, a, c, pos);
}
for(int c=a; c--;){
if(auto const d1=distance(c, a-1, pos); d1<=curDistance)
update(curDistance+d1, c, b, pos);
}
for(int dir=0; dir<4; ++dir){
auto const next=getMemory(pos, dir);
if(next!=loop and distance(a, b, next)>curDistance+1){
update(curDistance+1, a, b, next);
}
}
}
}
std::cout<<(result==INT_MAX ? -1: result)<<'\n';
}
