题解 P4205 【[NOI2005]智慧珠游戏 】
更好的阅读体验
暴力枚举+搜索剪枝
思路
其他三道题都没做，这道题
AC 了，不也不错吗？ --Mercury
搜索模拟测试考黑题，简直毒瘤。考场上用了两个多小时敲这道题，还差一个小剪枝才能
首先我们枚举每一种零件的放置方法，然后暴力枚举逐个判断每个位置上应该放哪个零件。为了提高枚举效率，我们规定放入的零件对上一行没有影响，也就是说，我们枚举每个位置放置的零件，也就是枚举该零件的左上角放置在该位置时是否有可行方案。
然而最后被这样的一组数据卡掉了：
.
..
...
....
.....
......
.......
.......J
......JJJ
.......J..显然，右下角什么都放不进去，而我的搜索是顺序搜索，所以一直要到快搜索完才会判断到右下角，我的程序也因此被卡到了（明明DLX才是正解好吧，神tm暴搜被卡） 。于是有这样的一个优化：对于当前局面如果最小联通块的大小
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('\n');
}
}
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;
}
}