腊鸡题目，实在卡不过去。
（改了一下午）
就是裸的斯坦纳树的题目，一方面合并子集，另一方面SPFA迭代求解。
优化了许多地方，甚至基数排序都写了。
还是T到死，不打算改了，就这样吧
#include <map>
#include <cmath>
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define F(i,j,k) for (int i=j;i<=k;++i)
#define D(i,j,k) for (int i=j;i>=k;--i)
#define inf 0x3f3f3f3f
#define maxn 502
#define ll long long
#define mp make_pair short n,r,c,a[maxn][maxn];
int dp[maxn][maxn][10][10];
char s[maxn][maxn];
short mov[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
short go[maxn][maxn][4][2]; void Readin()
{
memset(dp,0x3f,sizeof dp);
cin>>n>>c>>r;
F(i,1,r)
{
scanf("%s",s[i]+1);
F(j,1,c)
{
switch(s[i][j])
{
case '.':a[i][j]=0;break;
case 'x':a[i][j]=-1;break;
case 'A':a[i][j]=10;break;
case 'C':a[i][j]=11;break;
default: a[i][j]=s[i][j]-'0';dp[i][j][a[i][j]][a[i][j]]=0;break;
}
}
}
F(i,0,r) a[i][0]=a[i][c+1]=-1;F(i,0,c) a[0][i]=a[r+1][i]=-1; a[r+1][c+1]=-1;
} int vis[maxn][maxn][4],idx; void dfs(int nx,int ny,int k)
{
int tmp=k;
if (vis[nx][ny][k]==idx)
{
go[nx][ny][k][0]=-1;
go[nx][ny][k][1]=-1;
return;
}
vis[nx][ny][k]=idx;
if (go[nx][ny][k][0]!=0) return;
switch(a[nx][ny])
{
case 10:tmp=(tmp+3)%4;break;
case 11:tmp=(tmp+1)%4;break;
}
if (a[nx+mov[tmp][0]][ny+mov[tmp][1]]==-1)
{
go[nx][ny][k][0]=nx;
go[nx][ny][k][1]=ny;
return;
}
int tx=nx+mov[tmp][0],ty=ny+mov[tmp][1];
if (!go[tx][ty][tmp][0]) dfs(tx,ty,tmp);
go[nx][ny][k][0]=go[tx][ty][tmp][0];
go[nx][ny][k][1]=go[tx][ty][tmp][1];
} void init()
{
F(i,1,r) F(j,1,c)
F(k,0,3){
int nx=i,ny=j,flag=1;++idx;
dfs(nx,ny,k);
}
} struct Statement{short x,y,l,r; int v;}sta[maxn*maxn],res[maxn*maxn];
queue <Statement> q,d;
int top=0; bool Com(Statement a, Statement b)
{return a.v<b.v;} int cnt[200005],ctop=0; void Radix_Sort()
{
memset(cnt,0,sizeof cnt);
F(i,1,top)
{
if (sta[i].v>=200000) continue;
cnt[sta[i].v]++,ctop=max(ctop,sta[i].v);
}
F(i,1,ctop) cnt[i]+=cnt[i-1]; int tmp=cnt[ctop];
F(i,1,top)
{
if (sta[i].v>=200000) continue;
res[cnt[sta[i].v]--]=sta[i];
}
F(i,1,tmp) sta[i]=res[i];
memcpy(sta,res,(top+1)*sizeof(Statement));
} void SPFA()
{
// sort(sta+1,sta+top+1,Com);
Radix_Sort();
F(i,1,top) q.push(sta[i]);
while (!q.empty()||!d.empty())
{
int nx,ny,l,r,v;
if (d.empty()||(!d.empty()&&!q.empty()&&q.front().v<=d.front().v))
{
Statement now=q.front(); q.pop();
nx=now.x,ny=now.y,l=now.l,r=now.r,v=now.v;
}
else
{
Statement now=d.front(); d.pop();
nx=now.x,ny=now.y,l=now.l,r=now.r,v=now.v;
}
if (dp[nx][ny][l][r]<v) continue;
for (int k=0;k<4;++k)
if (go[nx][ny][k][0]!=-1)
{
int tx=go[nx][ny][k][0],ty=go[nx][ny][k][1];
if (dp[tx][ty][l][r]>dp[nx][ny][l][r]+1)
{
dp[tx][ty][l][r]=dp[nx][ny][l][r]+1;
Statement now;
now.x=tx;now.y=ty;now.l=l;now.r=r;now.v=dp[tx][ty][l][r];
d.push(now);
}
}
}
}
void DP()
{
F(i,1,r) F(j,1,c) if (a[i][j]>=1&&a[i][j]<=n)
{++top;sta[top].x=i;sta[top].y=j;sta[top].l=a[i][j];sta[top].r=a[i][j];sta[top].v=dp[i][j][a[i][j]][a[i][j]];}
SPFA();
F(len,2,n)
{
F(i,1,n-len+1)
{
top=0;
int j=i+len-1;
F(x,1,r) F(y,1,c)
{
F(z,i,j-1) dp[x][y][i][j]=min(dp[x][y][i][z]+dp[x][y][z+1][j],dp[x][y][i][j]);
if (dp[x][y][i][j]<inf)
{
Statement now;
now.x=x;now.y=y;now.l=i;now.r=j;now.v=dp[x][y][i][j];
sta[++top]=now;
}
}
SPFA();
}
}
int ans=inf;
F(i,1,r) F(j,1,c) ans=min(ans,dp[i][j][1][n]);
printf("%d\n",ans==inf?-1:ans);
} int main()
{
Readin();
init();
DP();
}