#include <bits/stdc++.h>
using namespace std;
struct component
{
int l, r; // range
int x, y; // pos
};
typedef vector<component> vc;
string encode(vc &comp)
{
string res;
for (auto i : comp)
{
res += to_string(i.l) + "," + to_string(i.r) + ",";
res += to_string(i.x) + "," + to_string(i.y) + "|";
}
return res;
}
bool compatable(const component &a, const component &b)
{
return (a.r + 1 == b.l or b.r + 1 == a.l);
}
bool compare(const component &a, const component &b)
{
if (a.l != b.l)
return a.l < b.l;
if (a.r != b.r)
return a.r < b.r;
if (a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
vc normilize(vc comp)
{
sort(comp.begin(), comp.end(), compare);
return comp;
}
vector<string> g;
vector<pair<int, int>> dirs = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}};
int w, h;
bool inside(int x, int y)
{
return (x >= 0 and y >= 0 and x < w and y < h);
}
pair<int, int> move(int sx, int sy, int dir)
{
int x = sx, y = sy, d = dir;
while (true)
{
int nx = x + dirs[d].first;
int ny = y + dirs[d].second;
if (!inside(nx, ny) or g[ny][nx] == 'x')
break;
x = nx;
y = ny;
if (g[ny][nx] == 'A')
d = (d + 3) % 4;
if (g[ny][nx] == 'C')
d = (d + 1) % 4;
}
return {x, y};
}
vc mergecomp(vc comps)
{
bool change = true;
while (change)
{
change = false;
for (int i = 0; i < comps.size(); i++)
{
for (int j = i + 1; j < comps.size(); j++)
{
if (not(comps[i].x == comps[j].x and
comps[i].y == comps[j].y and
compatable(comps[i], comps[j])))
continue;
component merged;
merged.x = comps[i].x, merged.y = comps[i].y;
merged.l = min(comps[i].l, comps[j].l);
merged.r = max(comps[i].r, comps[j].r);
vc nxt;
for (int k = 0; k < comps.size(); k++)
if (k != i and k != j)
nxt.push_back(comps[k]);
nxt.push_back(merged);
comps = nxt;
change = true;
break;
}
if (change)
break;
}
}
return normilize(comps);
}
int n;
int main()
{
// ios_base::sync_with_stdio(false);
// cin.tie(nullptr);
cin >> n >> w >> h;
vc start;
g.resize(h);
for (int i = 0; i < h; i++)
{
cin >> g[i];
for (int j = 0; j < w; j++)
if (g[i][j] >= '1' and g[i][j] <= '9')
{
int label = g[i][j] - '0';
start.push_back({label, label, j, i});
}
}
start = normilize(start);
queue<pair<vc, int>> q;
unordered_set<string> vis;
q.push({start, 0});
vis.insert(encode(start));
while (!q.empty())
{
auto comps = q.front().first;
auto dist = q.front().second;
q.pop();
if (comps.size() == 1 and comps[0].l == 1 and comps[0].r == n)
{
cout << dist << "\n";
return 0;
}
for (int i = 0; i < comps.size(); i++)
{
for (int d = 0; d < 4; d++)
{
vc newcomp = comps;
auto nxt = move(comps[i].x, comps[i].y, d);
newcomp[i].x = nxt.first, newcomp[i].y = nxt.second;
newcomp = mergecomp(newcomp);
string e = encode(newcomp);
if (vis.find(e) == vis.end())
{
vis.insert(e);
q.push({newcomp, dist + 1});
}
}
}
}
cout << "-1\n";
return 0;
}
