#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); } vector<vector<vector<pair<int, int>>>> moves; 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}; } void precompmoves(int w, int h) { moves.resize(w); for (int i = 0; i < w; i++) { moves[i].resize(h); for (int j = 0; j < h; j++) moves[i][j].resize(4); } for (int x = 0; x < w; x++) for (int y = 0; y < h; y++) for (int d = 0; d < 4; d++) moves[x][y][d] = move(x, y, d); } 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; struct StateKey { int sz; int data[36]; bool operator==(const StateKey &o) const { if (sz != o.sz) return false; for (int i = 0; i < sz; i++) if (data[i] != o.data[i]) return false; return true; } }; struct StateKeyHash { size_t operator()(const StateKey &k) const { size_t h = 0; for (int i = 0; i < k.sz; i++) h = h * 1315423911u + k.data[i]; return h; } }; StateKey make_key(const vc &comp) { StateKey k; k.sz = 0; for (auto &c : comp) { k.data[k.sz++] = c.l; k.data[k.sz++] = c.r; k.data[k.sz++] = c.x; k.data[k.sz++] = c.y; } return k; } 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}); } } precompmoves(w, h); start = normilize(start); queue<pair<vc, int>> q; q.push({start, 0}); unordered_set<StateKey, StateKeyHash> vis; vis.insert(make_key(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 = moves[comps[i].x][comps[i].y][d]; newcomp[i].x = nxt.first, newcomp[i].y = nxt.second; newcomp = mergecomp(newcomp); StateKey k = make_key(newcomp); if (vis.find(k) == vis.end()) { vis.insert(k); q.push({newcomp, dist + 1}); } } } } cout << "-1\n"; return 0; }