第一次听说斯坦纳树这种东西

先dfs预处理出来dis[i][j][k]表示格子(i,j)向k方向转移能到哪，记忆话搜索预处理，注意如果有环的话特判一下

设f[i][j][x][y]表示复合机器人i-j在(x,y)生成需要推得步数，用spfa转移，因为时间比较紧所以优化spfa，把能转移的放进一个队列（准确的来讲是栈）按f排序，spfa转移到的放到另一个，每次取队首小的更新答案

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=505,M=600003,dx[]={0,1,0,-1},dy[]={1,0,-1,0};

int n,h,w,f[10][10][N][N],v[N][N][5],ti,s[M+5],va[N*N],top,inf;

bool mk[N][N];

char c[N][N];

struct qwe

{

	int x,y;

	qwe(int X=0,int Y=0)

	{

		x=X,y=Y;

	}

}dis[N][N][5],q[N*N],p[M+5];

qwe dfs(int x,int y,int k)

{

	if(v[x][y][k]==ti)

		return qwe(-1,0);

	v[x][y][k]=ti;

	if(dis[x][y][k].x!=0)

		return dis[x][y][k];

	int t=k;

	if(c[x][y]=='C')

		k=(k+1)%4;

	if(c[x][y]=='A')

		k=(k+3)%4;

	int xx=x+dx[k],yy=y+dy[k];

	if(xx>w||xx<1||yy>h||yy<1||c[xx][yy]=='x')

		return dis[x][y][t]=qwe(x,y);

	return dis[x][y][t]=dfs(xx,yy,k);

}

void spfa(int l,int r)

{

	memset(s,0,sizeof(s));

	memset(mk,0,sizeof(mk));

	int mn=inf,mx=-inf;

	for(int i=1;i<=top;i++)

	{

		s[va[i]]++;

		if(va[i]<mn)

			mn=va[i];

		if(va[i]>mx)

			mx=va[i];

		mk[q[i].x][q[i].y]=1;

	}

	for(int i=mn+1;i<=mx;i++)

		s[i]+=s[i-1];

	for(int i=1;i<=top;i++)

		p[s[va[i]]--]=q[i];

	for(int i=1;i<=top;i++)

		q[i]=p[top-i+1];

	int ll=0,rr=0;

	while(top||ll!=rr)

	{

		int now=ll%M+1;

		qwe u;

		if(ll==rr||(top&&f[l][r][q[top].x][q[top].y]<f[l][r][p[now].x][p[now].y]))

			u=q[top--];

		else

			u=p[ll=now];

		int x=u.x,y=u.y;

		mk[x][y]=0;

		for(int i=0;i<4;i++)

		{

			int tx=dis[x][y][i].x,ty=dis[x][y][i].y;

			if(tx!=-1&&f[l][r][x][y]+1<f[l][r][tx][ty])

			{

				f[l][r][tx][ty]=f[l][r][x][y]+1;

				if(!mk[tx][ty])

				{

					mk[tx][ty]=1;

					p[rr=rr%M+1]=qwe(tx,ty);

				}

			}

		}

	}

}

int main()

{

	scanf("%d%d%d",&n,&h,&w);

	for(int i=1;i<=w;i++)

		scanf("%s",c[i]+1);

	memset(f,127/3,sizeof(f));

	inf=f[0][0][0][0];cerr<<inf<<endl;

	for(int i=1;i<=w;i++)

		for(int j=1;j<=h;j++)

			if(c[i][j]!='x')

				for(int k=0;k<4;k++)

					ti++,dis[i][j][k]=dfs(i,j,k);

	for(int i=1;i<=w;i++)

		for(int j=1;j<=h;j++)

			if(c[i][j]>='0'&&c[i][j]<='9')

				f[c[i][j]-48][c[i][j]-48][i][j]=0;

	for(int l=1;l<=n;l++)

		for(int x=1;x<=n-l+1;x++)

		{

			int y=x+l-1;top=0;

			for(int i=1;i<=w;i++)

				for(int j=1;j<=h;j++)

				{

					for(int k=x;k<y;k++)

						if(f[x][y][i][j]>f[x][k][i][j]+f[k+1][y][i][j])

							f[x][y][i][j]=f[x][k][i][j]+f[k+1][y][i][j];

					if(f[x][y][i][j]!=inf)

					{

						q[++top]=qwe(i,j);

						va[top]=f[x][y][i][j];

					}

				}

			spfa(x,y);

		}

	int ans=inf;

	for(int i=1;i<=w;i++)

		for(int j=1;j<=h;j++)

			if(f[1][n][i][j]<ans)

				ans=f[1][n][i][j];

	printf("%d\n",ans==inf?-1:ans);

	return 0;

}