题意
题目描述
智慧珠游戏拼盘由一个三角形盘件和(12)个形态各异的零件组成。拼盘的盘 件如图(1)所示
对于由珠子构成的零件，可以放到盘件的任一位置，条件是能有地方放，且尺寸合适，所有的零件都允许旋转((0º,90º,180º,270º))和翻转(水平、竖直)。
现给出一个盘件的初始布局，求一种可行的智慧珠摆放方案，使所有的零件都能放进盘件中。
输入输出格式
输入格式：
文件中包含初始的盘件描述，一共有(10)行，第(i)行有(i)个字符。如果第(i)行的第(j)个字符是字母“(A)”至“(L)”中的一个，则表示第(i)行第(j)列的格子上已经放了零件，零件的编号为对应的字母。如果第(i)行的第(j)个字符是“.”，则表示第(i)行第(j)列的格子上没有放零件。输入保证预放的零件已摆放在盘件中。
输出格式：
如果能找到解，向输出文件打印(10)行，为放完全部(12)个零件后的布局。其中，第(i)行应包含(i)个字符，第(i)行的第(j)个字符表示第(i)行第(j)列的格子上放的是哪个零件。如果无解，输出单独的一个字符串‘No solution’(不要引号，请注意大小写)。所有的数据保证最多只有一组解。
输入输出样例
输入样例：
.
..
...
....
.....
.....C
...CCC.
EEEHH...
E.HHH....
E.........
输出样例：
B
BK
BKK
BJKK
JJJDD
GJGDDC
GGGCCCI
EEEHHIIA
ELHHHIAAF
ELLLLIFFFF
思路
其他三道题都没做，这道题(AC)了，不也不错吗？ --Mercury
搜索模拟测试考黑题，简直毒瘤。考场上用了两个多小时敲这道题，还差一个小剪枝才能(AC)。
首先我们枚举每一种零件的放置方法，然后暴力枚举逐个判断每个位置上应该放哪个零件。为了提高枚举效率，我们规定放入的零件对上一行没有影响，也就是说，我们枚举每个位置放置的零件，也就是枚举该零件的左上角放置在该位置时是否有可行方案。
然而最后被这样的一组数据卡掉了：
.
..
...
....
.....
......
.......
.......J
......JJJ
.......J..
显然，右下角什么都放不进去，而我的搜索是顺序搜索，所以一直要到快搜索完才会判断到右下角，我的程序也因此被卡到了(8)秒 （明明(DLX)才是正解好吧，神tm暴搜被卡） 。于是有这样的一个优化：对于当前局面如果最小联通块的大小(leq 2)，那么就是不可行的方案，直接回溯。这样就可以很快地跑完了。
AC代码
#include<bits/stdc++.h>
using namespace std;
char G[15][15];
bool vis[26],hjj[15][15];
inline char readc()
{
char ch=getchar();
while(ch!='.'&&!isalpha(ch)) ch=getchar();
return ch;
}
inline void print()
{
for(int i=1;i<=10;i++)
{
for(int j=1;j<=i;j++) putchar(G[i][j]);
putchar('
');
}
}
bool judge(int x,int y,char z,int w)
{
if(z=='A')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y+1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.') return true;
return false;
}
else if(z=='B')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x][y+3]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+3][y]=='.') return true;
return false;
}
else if(z=='C')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y+1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y-2]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.') return true;
else if(w==4&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==5&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==6&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.') return true;
else if(w==7&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y-1]=='.') return true;
return false;
}
else if(z=='D')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.') return true;
return false;
}
else if(z=='E')
{
if(w==0&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.'&&G[x+2][y+2]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y+2]=='.'&&G[x+2][y+2]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y-1]=='.'&&G[x+2][y-2]=='.') return true;
return false;
}
else if(z=='F')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x][y+3]=='.'&&G[x+1][y+1]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+3][y]=='.'&&G[x+1][y-1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y-2]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.'&&G[x+3][y]=='.') return true;
else if(w==4&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==5&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x][y+3]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==6&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y]=='.'&&G[x+3][y]=='.') return true;
else if(w==7&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y-1]=='.'&&G[x+3][y]=='.') return true;
return false;
}
else if(z=='G')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x][y+2]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.') return true;
return false;
}
else if(z=='H')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y+1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y+1]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.') return true;
else if(w==4&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==5&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y]=='.') return true;
else if(w==6&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.') return true;
else if(w==7&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+2][y]=='.'&&G[x+2][y-1]=='.') return true;
return false;
}
else if(z=='I')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y+2]=='.'&&G[x+1][y+3]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y-1]=='.'&&G[x+3][y-1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.'&&G[x+1][y+3]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+2][y-1]=='.'&&G[x+3][y-1]=='.') return true;
else if(w==4&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.') return true;
else if(w==5&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+2][y+1]=='.'&&G[x+3][y+1]=='.') return true;
else if(w==6&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y-2]=='.') return true;
else if(w==7&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y+1]=='.'&&G[x+3][y+1]=='.') return true;
return false;
}
else if(z=='J')
{
if(w==0&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y]=='.') return true;
return false;
}
else if(z=='K')
{
if(w==0&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y+1]=='.'&&G[x+2][y+2]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+2][y-1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.'&&G[x+2][y+2]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+2][y-1]=='.'&&G[x+2][y-2]=='.') return true;
return false;
}
else if(z=='L')
{
if(w==0&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x][y+3]=='.'&&G[x+1][y]=='.') return true;
else if(w==1&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y+1]=='.'&&G[x+2][y+1]=='.'&&G[x+3][y+1]=='.') return true;
else if(w==2&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y-1]=='.'&&G[x+1][y-2]=='.'&&G[x+1][y-3]=='.') return true;
else if(w==3&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+3][y]=='.'&&G[x+3][y+1]=='.') return true;
else if(w==4&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+1][y+1]=='.'&&G[x+1][y+2]=='.'&&G[x+1][y+3]=='.') return true;
else if(w==5&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+3][y]=='.') return true;
else if(w==6&&G[x][y]=='.'&&G[x][y+1]=='.'&&G[x][y+2]=='.'&&G[x][y+3]=='.'&&G[x+1][y+3]=='.') return true;
else if(w==7&&G[x][y]=='.'&&G[x+1][y]=='.'&&G[x+2][y]=='.'&&G[x+3][y]=='.'&&G[x+3][y-1]=='.') return true;
return false;
}
return false;
}
void fill(int x,int y,char z,int w)
{
if(z=='A')
{
if(w==0) G[x][y]=G[x][y+1]=G[x+1][y]='A';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]='A';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y-1]='A';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y+1]='A';
}
else if(z=='B')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]='B';
else if(w==1) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]='B';
}
else if(z=='C')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]='C';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+2][y+1]='C';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y-2]='C';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]='C';
else if(w==4) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]='C';
else if(w==5) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+2]='C';
else if(w==6) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+2][y]='C';
else if(w==7) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]='C';
}
else if(z=='D') G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]='D';
else if(z=='E')
{
if(w==0) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]=G[x+2][y+2]='E';
else if(w==1) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+2][y]='E';
else if(w==2) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+2]=G[x+2][y+2]='E';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]=G[x+2][y-2]='E';
}
else if(z=='F')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y+1]='F';
else if(w==1) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]=G[x+1][y-1]='F';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+1][y-1]=G[x+1][y-2]='F';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]=G[x+3][y]='F';
else if(w==4) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y+1]=G[x+1][y+2]='F';
else if(w==5) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y+2]='F';
else if(w==6) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y]=G[x+3][y]='F';
else if(w==7) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]=G[x+3][y]='F';
}
else if(z=='G')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+1][y+2]='G';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+2][y]=G[x+2][y+1]='G';
else if(w==2) G[x][y]=G[x][y+2]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]='G';
else if(w==3) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]='G';
}
else if(z=='H')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+1][y+1]='H';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]=G[x+2][y+1]='H';
else if(w==2) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y-1]=G[x+1][y+1]='H';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y]=G[x+2][y+1]='H';
else if(w==4) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]='H';
else if(w==5) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]=G[x+2][y]='H';
else if(w==6) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+1]=G[x+1][y+2]='H';
else if(w==7) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+2][y]=G[x+2][y-1]='H';
}
else if(z=='I')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+2]=G[x+1][y+3]='I';
else if(w==1) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]=G[x+3][y-1]='I';
else if(w==2) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+1][y+2]=G[x+1][y+3]='I';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+2][y-1]=G[x+3][y-1]='I';
else if(w==4) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+1][y-1]='I';
else if(w==5) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]=G[x+3][y+1]='I';
else if(w==6) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y-1]=G[x+1][y-2]='I';
else if(w==7) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y+1]=G[x+3][y+1]='I';
}
else if(z=='J') G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y+1]=G[x+2][y]='J';
else if(z=='K')
{
if(w==0) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y+1]=G[x+2][y+2]='K';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y-1]=G[x+2][y-1]='K';
else if(w==2) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+1][y+2]=G[x+2][y+2]='K';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+2][y-1]=G[x+2][y-2]='K';
}
else if(z=='L')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y]='L';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+2][y+1]=G[x+3][y+1]='L';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y-2]=G[x+1][y-3]='L';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]=G[x+3][y+1]='L';
else if(w==4) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]=G[x+1][y+3]='L';
else if(w==5) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+2][y]=G[x+3][y]='L';
else if(w==6) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y+3]='L';
else if(w==7) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]=G[x+3][y-1]='L';
}
}
void unfill(int x,int y,char z,int w)
{
if(z=='A')
{
if(w==0) G[x][y]=G[x][y+1]=G[x+1][y]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]='.';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y-1]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y+1]='.';
}
else if(z=='B')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]='.';
else if(w==1) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]='.';
}
else if(z=='C')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+2][y+1]='.';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y-2]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]='.';
else if(w==4) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]='.';
else if(w==5) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+2]='.';
else if(w==6) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+2][y]='.';
else if(w==7) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]='.';
}
else if(z=='D') G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]='.';
else if(z=='E')
{
if(w==0) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]=G[x+2][y+2]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+2][y]='.';
else if(w==2) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+2]=G[x+2][y+2]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]=G[x+2][y-2]='.';
}
else if(z=='F')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y+1]='.';
else if(w==1) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]=G[x+1][y-1]='.';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+1][y-1]=G[x+1][y-2]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]=G[x+3][y]='.';
else if(w==4) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y+1]=G[x+1][y+2]='.';
else if(w==5) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y+2]='.';
else if(w==6) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y]=G[x+3][y]='.';
else if(w==7) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]=G[x+3][y]='.';
}
else if(z=='G')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+1][y+2]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+2][y]=G[x+2][y+1]='.';
else if(w==2) G[x][y]=G[x][y+2]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]='.';
else if(w==3) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]='.';
}
else if(z=='H')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+1][y+1]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]=G[x+2][y+1]='.';
else if(w==2) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y-1]=G[x+1][y+1]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y]=G[x+2][y+1]='.';
else if(w==4) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]='.';
else if(w==5) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y+1]=G[x+2][y]='.';
else if(w==6) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+1]=G[x+1][y+2]='.';
else if(w==7) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+2][y]=G[x+2][y-1]='.';
}
else if(z=='I')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y+2]=G[x+1][y+3]='.';
else if(w==1) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y-1]=G[x+3][y-1]='.';
else if(w==2) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+1][y+2]=G[x+1][y+3]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+2][y-1]=G[x+3][y-1]='.';
else if(w==4) G[x][y]=G[x][y+1]=G[x][y+2]=G[x+1][y]=G[x+1][y-1]='.';
else if(w==5) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+2][y+1]=G[x+3][y+1]='.';
else if(w==6) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y-1]=G[x+1][y-2]='.';
else if(w==7) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y+1]=G[x+3][y+1]='.';
}
else if(z=='J') G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y+1]=G[x+2][y]='.';
else if(z=='K')
{
if(w==0) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+2][y+1]=G[x+2][y+2]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+1][y-1]=G[x+2][y-1]='.';
else if(w==2) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+1][y+2]=G[x+2][y+2]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+2][y-1]=G[x+2][y-2]='.';
}
else if(z=='L')
{
if(w==0) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y]='.';
else if(w==1) G[x][y]=G[x][y+1]=G[x+1][y+1]=G[x+2][y+1]=G[x+3][y+1]='.';
else if(w==2) G[x][y]=G[x+1][y]=G[x+1][y-1]=G[x+1][y-2]=G[x+1][y-3]='.';
else if(w==3) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]=G[x+3][y+1]='.';
else if(w==4) G[x][y]=G[x+1][y]=G[x+1][y+1]=G[x+1][y+2]=G[x+1][y+3]='.';
else if(w==5) G[x][y]=G[x][y+1]=G[x+1][y]=G[x+2][y]=G[x+3][y]='.';
else if(w==6) G[x][y]=G[x][y+1]=G[x][y+2]=G[x][y+3]=G[x+1][y+3]='.';
else if(w==7) G[x][y]=G[x+1][y]=G[x+2][y]=G[x+3][y]=G[x+3][y-1]='.';
}
}
int ltk(int x,int y)
{
hjj[x][y]=true;int re=1;
if(G[x-1][y]=='.'&&!hjj[x-1][y]) re+=ltk(x-1,y);
if(G[x][y-1]=='.'&&!hjj[x][y-1]) re+=ltk(x,y-1);
if(G[x+1][y]=='.'&&!hjj[x+1][y]) re+=ltk(x+1,y);
if(G[x][y+1]=='.'&&!hjj[x][y+1]) re+=ltk(x,y+1);
return re;
}
bool dfs(int x,int y)
{
memset(hjj,false,sizeof hjj);
for(int i=1;i<=10;i++)
for(int j=1;j<=i;j++)
if(G[i][j]=='.'&&!hjj[i][j])
if(ltk(i,j)<=2) return false;
for(char i='A';i<='L';i++)
{
if(vis[i-'A']) continue;
for(int w=0;w<8;w++)
if(judge(x,y,i,w))
{
vis[i-'A']=true;
fill(x,y,i,w);
bool flag=false;
for(int j=1;j<=10;j++)
{
for(int k=1;k<=j;k++)
if(G[j][k]=='.')
{
flag=true;
if(dfs(j,k)) return true;
break;
}
if(flag) break;
}
if(!flag) return true;
vis[i-'A']=false;
unfill(x,y,i,w);
}
}
return false;
}
int main()
{
for(int i=1;i<=10;i++)
{
for(int j=1;j<=i;j++)
{
G[i][j]=readc();
if(isalpha(G[i][j])) vis[G[i][j]-'A']=true;
}
for(int j=i+1;j<=10;j++)
G[i][j]='$';
}
for(int i=0;i<=11;i++) G[i][0]=G[i][11]=G[0][i]=G[11][i]='$';
for(int i=1;i<=10;i++)
for(int j=1;j<=i;j++)
if(G[i][j]=='.')
{
if(dfs(i,j)) print();
else printf("No solution");
return 0;
}
}