rt，感觉该用的都用了，样例本机跑了20s。

#include <bits/stdc++.h>
using namespace std;
int g[20][20]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
               {0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
               {0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
               {0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
               {0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4},
               {0,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8},
               {0,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8},
               {0,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8},
               {0,5,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8},
               {0,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12},
               {0,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12},
               {0,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12},
               {0,9,9,9,9,10,10,10,10,11,11,11,11,12,12,12,12},
               {0,13,13,13,13,14,14,14,14,15,15,15,15,16,16,16,16},
               {0,13,13,13,13,14,14,14,14,15,15,15,15,16,16,16,16},
               {0,13,13,13,13,14,14,14,14,15,15,15,15,16,16,16,16},
               {0,13,13,13,13,14,14,14,14,15,15,15,15,16,16,16,16}};
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
int s=0,flag=0,m[20],tx[20],ty[20];
char map1[20][20];
bitset<20>c[20][20],ck;
bool book[20][20];
void gq(int x,int y,int k)
{
	c[x][y][k]=1,book[x][y]=1;
	for(int i=0;i<4;i++)
	    {
	    	int tx=x+dx[i],ty=y+dy[i];
	    	if(g[tx][ty]!=g[x][y]||book[tx][ty])continue;
	    	gq(tx,ty,k);
		}
}

bool gj(int x,int y)
{
	bool res=0;
	if(map1[x][y]=='-')
	   {
	   for(int k=0;k<16;k++)
	       if(!c[x][y][k])m[k]++,tx[k]=x,ty[k]=y;
	   res=1;
       }
	ck&=c[x][y],book[x][y]=1;
	for(int i=0;i<4;i++)
	    {
	    	int tx=x+dx[i],ty=y+dy[i];
	    	if(g[tx][ty]!=g[x][y]||book[tx][ty])continue;
	    	res|=gj(tx,ty);
		}
	return res;
}

void fill(int i,int j,int id)
{
	memset(book,0,sizeof(book));
	for(int k=1;k<=16;k++)c[i][k][id]=1;
	for(int k=1;k<=16;k++)c[k][j][id]=1;
	gq(i,j,id);
}

void dfs(int now)
{
	int ch=0,px=0,py=0;
	char cop[20][20];
	bitset<20>coy[20][20];
	if(flag)return;
	for(int i=1;i<=16;i++)
	    for(int j=1;j<=16;j++)
	        cop[i][j]=map1[i][j],coy[i][j]=c[i][j];
	for(int i=1;i<=16;i++)
	    for(int j=1;j<=16;j++)
	        if(map1[i][j]=='-'&&c[i][j].count()==15)
	           {
	           for(int k=0;k<16;k++)
	           	    {
					  if(c[i][j][k])continue;
					  map1[i][j]='A'+k;
	                  fill(i,j,k);
					}
				now++;
			   }
	for(int i=1;i<=16;i++)
	    for(int j=1;j<=16;j++)
	        if(map1[i][j]=='-'&&c[i][j].count()==16)
	            {
	            for(int i=1;i<=16;i++)
				    for(int j=1;j<=16;j++)
				        map1[i][j]=cop[i][j],c[i][j]=coy[i][j];
			    return;
			    }
    for(int i=1;i<=16;i++)
	    {
	    bool t=0;
	    ck.set();
	    for(int j=0;j<16;j++)m[j]=0,tx[j]=0,ty[j]=0;
	    for(int j=1;j<=16;j++)
	        if(map1[i][j]=='-')
	           {
	           for(int k=0;k<16;k++)
	               if(!c[i][j][k])m[k]++,tx[k]=i,ty[k]=j;
			   ck&=c[i][j],t=1;
		       }
		if(t&&ck.count()==16)
		   {
	       for(int i=1;i<=16;i++)
			   for(int j=1;j<=16;j++)
				   map1[i][j]=cop[i][j],c[i][j]=coy[i][j];
		   return;
		   }
		for(int j=0;j<16;j++)
		    if(m[j]==1)
		       {
		       	map1[tx[j]][ty[j]]='A'+j;
	            fill(tx[j],ty[j],j);
	            now++;
			   }
	    }
	for(int i=1;i<=16;i++)
	    {
	    bool t=0;
	    ck.set();
	    for(int j=0;j<16;j++)m[j]=0,tx[j]=0,ty[j]=0;
	    for(int j=1;j<=16;j++)
	        {
	        for(int k=0;k<16;k++)
	            if(!c[j][i][k])m[k]++,tx[k]=j,ty[k]=i;
	        if(map1[j][i]=='-')ck&=c[j][i],t=1;
	        }
		if(t&&ck.count()==16)
		   {
	       for(int i=1;i<=16;i++)
			   for(int j=1;j<=16;j++)
				   map1[i][j]=cop[i][j],c[i][j]=coy[i][j];
		   return;
		   }
		for(int j=0;j<16;j++)
		    if(m[j]==1)
		       {
		       	map1[tx[j]][ty[j]]='A'+j;
	            fill(tx[j],ty[j],j);
	            now++;
			   }
	    }
	memset(book,0,sizeof(book));
	for(int i=1;i<=16;i++)
	    for(int j=1;j<=16;j++)
	        if(!book[i][j])
	           {
	           	ck.set();
	           	for(int j=0;j<16;j++)m[j]=0,tx[j]=0,ty[j]=0;
	           	bool t=gj(i,j);
		        if(t&&ck.count()==16)
		           {
			       for(int i=1;i<=16;i++)
					   for(int j=1;j<=16;j++)
						   map1[i][j]=cop[i][j],c[i][j]=coy[i][j];
				   return;
				   }
				for(int j=0;j<16;j++)
				    if(m[j]==1)
				       {
				       	map1[tx[j]][ty[j]]='A'+j;
			            fill(tx[j],ty[j],j);
			            now++;
					   }
			   }
	if(now==256)
	   {
	   	flag=1;
	   	for(int i=1;i<=16;i++)printf("%s\n",map1[i]+1);
	   	return;
	   }
	for(int i=1;i<=16;i++)
	    for(int j=1;j<=16;j++)
	        if(map1[i][j]=='-'&&c[i][j].count()>ch)ch=c[i][j].count(),px=i,py=j;
	for(int i=1;i<=16;i++)
	    for(int j=1;j<=16;j++)
	        cop[i][j]=map1[i][j],coy[i][j]=c[i][j];
	for(int k=0;k<16;k++)
	    {
	    if(flag)return;
	    if(c[px][py][k])continue;
	    map1[px][py]='A'+k;
	    fill(px,py,k);
	    dfs(now+1);
	    for(int i=1;i<=16;i++)
		    for(int j=1;j<=16;j++)
		        map1[i][j]=cop[i][j],c[i][j]=coy[i][j];
		}
}

int main()
{
	while(scanf("%s",map1[1]+1)!=-1)
		{
			for(int i=1;i<=16;i++)
		        for(int j=1;j<=16;j++)c[i][j].reset();
			flag=0,s=0;
			for(int i=2;i<=16;i++)scanf("%s",map1[i]+1);
			for(int i=1;i<=16;i++)
			    for(int j=1;j<=16;j++)
			        if(map1[i][j]!='-')
			           {
			           	s++;
			           	fill(i,j,map1[i][j]-'A');
					   }
			dfs(s);
		}
}