$\text{RT}$，写了两个小时，用了一些玄学搞字典序的方法弄到了九十分，但是第二个点就是不明白为啥错了。

思路：$k$ 遍 $bfs$ 找出每一个点到其他点的最短距离，然后正常状压DP，记录前驱和前驱的状态，最后全部比较一遍，找到答案最下的并且答案最小的。

求查错，有什么能便捷找字典序最小的方法也可以说一说qwq

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<algorithm>
#include<map>
#include<vector>
using namespace std;
const int N=5e2+9;
const int M=20;
const int K=(1<<16)+9;
const int dx[]={0,0,1,-1};
const int dy[]={1,-1,0,0};
struct node{
	int last;
	int to;
	int dis;
}e[(M*M)<<1];
struct Node{
	int x,y;
};
int head[N],cnt;
int n,m,k,U,x[N],y[N];
char s[N][N];
bool vis[N];
int a[N][N],dis[N];
int f[M][K],pre2[M][K],pre1[M][K];
char mid[N],Put[N];
int top; 
int read()
{
	int f=1,x=0;
	char s=getchar();
	while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
	while(s>='0'&&s<='9'){x=(x<<1)+(x<<3)+(s^'0');s=getchar();}
	return f*x;
}
void add(int from,int to,int dis)
{
	e[++cnt].last=head[from];
	e[cnt].to=to;
	e[cnt].dis=dis;
	head[from]=cnt;
}
bool ok(int x,int y)
{
	if(x<1 or x>n or y<1 or y>n)
		return false;
	return true;
}
void bfs(int x,int y)
{
	queue<Node> q;
	q.push((Node){x,y});
	while(!q.empty())
	{
		Node cun=q.front();
		q.pop();
		int ax=cun.x;
		int ay=cun.y;
		if(s[ax][ay]>='A' and s[ax][ay]<='Z')
		{
			int Id=s[ax][ay]-'A'+1;
			dis[Id]=min(dis[Id],a[ax][ay]);//更新距离 
		}
		for(int i=0;i<=3;i++)
		{
			int kx=ax+dx[i];
			int ky=ay+dy[i];
			if(!ok(kx,ky)) continue;
			if(s[kx][ky]=='*') continue;
			if(a[kx][ky] > a[ax][ay] + 1)
			{
				a[kx][ky] = a[ax][ay] + 1;
				q.push((Node){kx,ky});	
			} 
		}
	}
}
void spfa()
{
	memset(f,127,sizeof(f));
	f[1][1]=0; vis[1]=true;
	queue<int> q; q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=head[u];i;i=e[i].last)
		{
			int v=e[i].to;
			int w=e[i].dis;
			for(int s=1;s<=U;s++)
			{
				if(s & (1<<(v-1))) continue;
				if(!(s & (1<<(u-1)))) continue;
				int Now=(s | (1<<(v-1)));
				if(f[v][Now] > f[u][s] + w)
				{
					f[v][Now] = f[u][s] + w;
					pre2[v][Now] = u;
					pre1[v][Now] = s;
					if(!vis[v])
					{
						q.push(v);
						vis[v]=true;	
					}
				} 
				if(f[v][Now] == f[u][s] + w)//保证字典序更小 
				{
					if(pre2[v][Now] < u)
					{
						pre2[v][Now] = u;
						pre1[v][Now] = s;
					}
				}
			} 
		}
	} 
}
bool cmp(char s1[],char s2[])
{
	for(int i=1;i<=k;i++)
	{
		if(s1[i]<s2[i])
			return false;//不交换 
		if(s1[i]>s2[i])
			return true;//交换 
	}
	return false;
}
int main()
{
	n=read(); m=read(); k=read(); U=(1<<k)-1;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
		{
			cin>>s[i][j];
			if(s[i][j]>='A' and s[i][j]<='Z')
			{
				x[s[i][j]-'A'+1]=i;
				y[s[i][j]-'A'+1]=j;
			}
		}
	for(int i=1;i<=k;i++)
	{
		memset(dis,0x3f3f3f3f,sizeof(dis));
		memset(a,0x3f3f3f3f,sizeof(a)); 
		a[x[i]][y[i]]=0; dis[i]=0;
		bfs(x[i],y[i]);
		for(int j=i+1;j<=k;j++)
		{
			//cout<<" i = "<<i<<" j = "<<j<<" w = "<<dis[j]<<endl;
			add(i,j,dis[j]);
			add(j,i,dis[j]);
		}
	}
	spfa();
	int ans=0x3f3f3f3f; //初始化 
	int Now=U,Id=2,last=0,top=k;
	for(;Now;)
	{
		Put[top--]=('A'+Id-1);
		last=Now;
		Now=pre1[Id][last];
		Id=pre2[Id][last];
	}
	ans=f[2][U];
	
	for(int i=3;i<=k;i++)
	{
		Now=U; Id=i; last=0; top=k;
		for(;Now;)
		{
			mid[top--]=('A'+Id-1);
			last=Now;
			Now=pre1[Id][last];
			Id=pre2[Id][last];
		}
		if(ans>f[i][U])
		{
			for(int j=1;j<=k;j++)
				Put[j]=mid[j];
			ans=f[i][U];
		}
		else if(ans==f[i][U])
			if(cmp(Put,mid))
				for(int j=1;j<=k;j++)
					Put[j]=mid[j]; 
	}
	cout<<ans<<endl;
	for(int i=1;i<=k;i++)
		cout<<Put[i]; 
	return 0;
}