#include <bits/stdc++.h>
#define ll long long
#define ff first
#define ss second
#define INF INT_MAX
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define FAR(i, a, b) for (int i = (a); i >= (b); i--)
#define all(x) (x.begin(), x.end())
const int MOD = 1e9 + 7;
using namespace std;
int n, w, h;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
pair<int, int> m[500][500][4];
char s[501][501];
vector<pair<int, int>> g[500][500];
int cost[10][10][500][500];
pair<int, int> dfs(int x, int y, int d)
{
if (x < 0)
return {x + 1, y};
if (y < 0)
return {x, y + 1};
if (x >= h)
return {x - 1, y};
if (y >= w)
return {x, y - 1};
if (s[x][y] == 'x')
return {x + dx[d * d], y + dy[d * d]};
if (m[x][y][d] != pair<int, int>{-1, -1})
return m[x][y][d];
int d2 = d;
if (s[x][y] == 'A')
d2 += 3, d2 &= 3;
else if (s[x][y] == 'C')
d2 += 1, d2 &= 3;
m[x][y][d] = {-2, -2};
return m[x][y][d] = dfs(x + dx[d2], y + dy[d2], d2);
}
void bfs(int u, int v)
{
auto c = cost[u][v];
for (int k = u + 1; k < v; k++)
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
c[i][j] = min(c[i][j], cost[u][k][i][j] + cost[k][v][i][j]);
queue<array<int, 3>> q;
vector<array<int, 3>> q2;
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (c[i][j] != INF)
q2.push_back({c[i][j], i, j});
sort(q2.begin(), q2.end(), greater<array<int, 3>>());
while (q.size() || q2.size())
{
bool ok = 0;
if (!q2.size())
ok = 1;
else if (q.size() && q.front()[0] < q2.back()[0])
ok = 1;
auto [cost, x, y] = ok ? q.front() : q2.back();
if (ok)
q.pop();
else
q2.pop_back();
for (auto [x2, y2] : g[x][y])
{
c[x2][y2] = min(c[x2][y2], cost + 1);
if (c[x2][y2])
q.push({c[x2][y2], x2, y2});
}
}
}
int main()
{
for (int i = 0; i < 500; i++)
for (int j = 0; j < 500; j++)
for (int d = 0; d < 4; d++)
m[i][j][d].ff = m[i][j][d].ss = 255;
for (int i = 0; i < 10; i++)
for (int j = 0; j < 10; j++)
for (int d = 0; d < 500; d++)
for (int k = 0; k < 500; k++)
cost[i][j][d][k] = 51;
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
for (int d = 0; d < 4; d++)
dfs(i, j, d);
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
for (int d = 0; d < 4; d++)
if (m[i][j][d] != pair<int, int>{-2, -2} && m[i][j][d] != pair<int, int>{i, j})
g[i][j].push_back(m[i][j][d]);
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
if (isdigit(s[i][j]))
cost[s[i][j] - '1'][s[i][j] - '0'][i][j] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= n - i; j++)
bfs(j, j + i);
int ans = INF;
for (int i = 0; i < h; i++)
for (int j = 0; j < w; j++)
ans = min(ans, cost[0][n][i][j]);
cout << ((ans == INF) ? -1 : ans) << endl;
return 0;
}
