【NOI2005】智慧珠游戏
mrsrz
10月 17, 2019
搜索
题目大意：
给定一个三角形，每个点是一个空位。现在有 $12$ 个形状不同的零件，要放到三角形里且需要恰好完全覆盖。
现在给出初始状态，问合法的解。保证解不超过一个。
题解：
暴力搜索。
先把智慧珠可能的 $60$ 种摆法预处理出来（可以通过初始状态进行变换，也可以直接打表）。
然后搜索，每次找到最上面，最左边的空格，考虑用一种方法填充。枚举即可。
我们来剪枝。
发现如果有大小为 $1,2,6$ 的连通块，那么显然是不存在解的。所以可以每次用并查集求出所有连通块大小，然后如果出现 $1,2,6$ 则直接退出当前递归。
加上这个剪枝就可以通过辣！
打表的代码，$6\rm KB$ 左右，行数超过五百。感觉也不多。
Code：
/*
By mrsrz
500+ lines
2019-10-17
*/
#include<iostream>
#include<cstdlib>
using namespace std;
struct block{
int r,c;
bool b[11][11];
char ch;int y;
}b[100];
char mp[11][11];
bool use[127];
int Id[11][11],tot;
inline bool can_put(int r,int c,int id){
if(c<0)return 0;
for(int i=0;i<b[id].r;++i){
for(int j=0;j<b[id].c;++j)
if(b[id].b[i][j]){
int x=r+i,y=c+j;
if(x>=10||y>x)return 0;
if(mp[x][y]!='.')return 0;
}
}
return 1;
}
inline void fill(int r,int c,int id){
for(int i=0;i<b[id].r;++i){
for(int j=0;j<b[id].c;++j)
if(b[id].b[i][j]){
int x=r+i,y=c+j;
mp[x][y]=b[id].ch;
}
}
}
inline void clear(int r,int c,int id){
for(int i=0;i<b[id].r;++i){
for(int j=0;j<b[id].c;++j)
if(b[id].b[i][j]){
int x=r+i,y=c+j;
mp[x][y]='.';
}
}
}
int fa[121],sz[121];
bool vs[121];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void judge(){
for(int i=1;i<=tot;++i)fa[i]=i,sz[i]=1,vs[i]=0;
for(int i=0;i<10;++i)
for(int j=0;j<=i;++j)if(mp[i][j]=='.'){
int u=find(Id[i][j]);
if(j-1>=0&&mp[i][j-1]=='.'){
int v=find(Id[i][j-1]);
if(u!=v)sz[u]+=sz[v],fa[v]=u;
}
if(i-1>=j&&mp[i-1][j]=='.'){
int v=find(Id[i-1][j]);
if(u!=v)sz[u]+=sz[v],fa[v]=u;
}
}else fa[Id[i][j]]=0,sz[Id[i][j]]=0;
for(int i=1;i<=tot;++i)
if(i==find(i))vs[sz[i]]=1;
}
void dfs(char nw){
if(nw==12){
for(int i=0;i<10;++i)
cout<<mp[i]<<'\n';
exit(0);
}
judge();
if(vs[1]||vs[2]||vs[6])return;
int xx=-1,yy=-1;
for(int i=0;i<10&&xx==-1;++i)
for(int j=0;j<=i;++j)
if(mp[i][j]=='.'){
xx=i,yy=j;
break;
}
for(int blk=1;blk<=60;++blk)
if(!use[b[blk].ch])
if(can_put(xx,yy-b[blk].y,blk)){
use[b[blk].ch]=1;
fill(xx,yy-b[blk].y,blk);
dfs(nw+1);
clear(xx,yy-b[blk].y,blk);
use[b[blk].ch]=0;
}
}
int main(){
b[1]=(block){
2,2,{
{1,1},
{1,0}
},'A',0
};
b[2]=(block){
2,2,{
{1,1},
{0,1}
},'A',0
};
b[3]=(block){
2,2,{
{0,1},
{1,1}
},'A',1
};
b[4]=(block){
2,2,{
{1,0},
{1,1}
},'A',0
};
b[5]=(block){
1,4,{
{1,1,1,1}
},'B',0
};
b[6]=(block){
4,1,{
{1},
{1},
{1},
{1}
},'B',0
};
b[7]=(block){
2,3,{
{1,1,1},
{1,0,0}
},'C',0
};
b[8]=(block){
2,3,{
{1,1,1},
{0,0,1}
},'C',0
};
b[9]=(block){
2,3,{
{1,0,0},
{1,1,1}
},'C',0
};
b[10]=(block){
2,3,{
{0,0,1},
{1,1,1}
},'C',2
};
b[11]=(block){
3,2,{
{1,1},
{1,0},
{1,0}
},'C',0
};
b[12]=(block){
3,2,{
{1,1},
{0,1},
{0,1}
},'C',0
};
b[13]=(block){
3,2,{
{1,0},
{1,0},
{1,1}
},'C',0
};
b[14]=(block){
3,2,{
{0,1},
{0,1},
{1,1}
},'C',1
};
b[15]=(block){
2,2,{
{1,1},
{1,1}
},'D',0
};
b[16]=(block){
3,3,{
{1,0,0},
{1,0,0},
{1,1,1}
},'E',0
};
b[17]=(block){
3,3,{
{1,1,1},
{1,0,0},
{1,0,0}
},'E',0
};
b[18]=(block){
3,3,{
{1,1,1},
{0,0,1},
{0,0,1}
},'E',0
};
b[19]=(block){
3,3,{
{0,0,1},
{0,0,1},
{1,1,1}
},'E',2
};
b[20]=(block){
2,4,{
{1,1,1,1},
{0,1,0,0}
},'F',0
};
b[21]=(block){
2,4,{
{1,1,1,1},
{0,0,1,0}
},'F',0
};
b[22]=(block){
2,4,{
{0,1,0,0},
{1,1,1,1}
},'F',1
};
b[23]=(block){
2,4,{
{0,0,1,0},
{1,1,1,1}
},'F',2
};
b[24]=(block){
4,2,{
{1,0},
{1,1},
{1,0},
{1,0}
},'F',0
};
b[25]=(block){
4,2,{
{1,0},
{1,0},
{1,1},
{1,0}
},'F',0
};
b[26]=(block){
4,2,{
{0,1},
{1,1},
{0,1},
{0,1}
},'F',1
};
b[27]=(block){
4,2,{
{0,1},
{0,1},
{1,1},
{0,1}
},'F',1
};
b[28]=(block){
2,3,{
{1,1,1},
{1,0,1}
},'G',0
};
b[29]=(block){
2,3,{
{1,0,1},
{1,1,1}
},'G',0
};
b[30]=(block){
3,2,{
{1,1},
{1,0},
{1,1}
},'G',0
};
b[31]=(block){
3,2,{
{1,1},
{0,1},
{1,1}
},'G',0
};
b[32]=(block){
2,3,{
{1,1,1},
{1,1,0}
},'H',0
};
b[33]=(block){
2,3,{
{1,1,1},
{0,1,1}
},'H',0
};
b[34]=(block){
2,3,{
{1,1,0},
{1,1,1}
},'H',0
};
b[35]=(block){
2,3,{
{0,1,1},
{1,1,1}
},'H',1
};
b[36]=(block){
3,2,{
{1,1},
{1,1},
{1,0}
},'H',0
};
b[37]=(block){
3,2,{
{1,1},
{1,1},
{0,1}
},'H',0
};
b[38]=(block){
3,2,{
{1,0},
{1,1},
{1,1}
},'H',0
};
b[39]=(block){
3,2,{
{0,1},
{1,1},
{1,1}
},'H',1
};
b[40]=(block){
2,4,{
{1,1,1,0},
{0,0,1,1}
},'I',0
};
b[41]=(block){
2,4,{
{0,0,1,1},
{1,1,1,0}
},'I',2
};
b[42]=(block){
2,4,{
{0,1,1,1},
{1,1,0,0}
},'I',1
};
b[43]=(block){
2,4,{
{1,1,0,0},
{0,1,1,1}
},'I',0
};
b[44]=(block){
4,2,{
{1,0},
{1,0},
{1,1},
{0,1}
},'I',0
};
b[45]=(block){
4,2,{
{0,1},
{0,1},
{1,1},
{1,0}
},'I',1
};
b[46]=(block){
4,2,{
{0,1},
{1,1},
{1,0},
{1,0}
},'I',1
};
b[47]=(block){
4,2,{
{1,0},
{1,1},
{0,1},
{0,1}
},'I',0
};
b[48]=(block){
3,3,{
{0,1,0},
{1,1,1},
{0,1,0}
},'J',1
};
b[49]=(block){
3,3,{
{1,0,0},
{1,1,0},
{0,1,1}
},'K',0
};
b[50]=(block){
3,3,{
{0,1,1},
{1,1,0},
{1,0,0}
},'K',1
};
b[51]=(block){
3,3,{
{1,1,0},
{0,1,1},
{0,0,1}
},'K',0
};
b[52]=(block){
3,3,{
{0,0,1},
{0,1,1},
{1,1,0}
},'K',2
};
b[53]=(block){
2,4,{
{1,1,1,1},
{1,0,0,0}
},'L',0
};
b[54]=(block){
2,4,{
{1,1,1,1},
{0,0,0,1}
},'L',0
};
b[55]=(block){
2,4,{
{1,0,0,0},
{1,1,1,1}
},'L',0
};
b[56]=(block){
2,4,{
{0,0,0,1},
{1,1,1,1}
},'L',3
};
b[57]=(block){
4,2,{
{1,1},
{1,0},
{1,0},
{1,0}
},'L',0
};
b[58]=(block){
4,2,{
{1,0},
{1,0},
{1,0},
{1,1}
},'L',0
};
b[59]=(block){
4,2,{
{1,1},
{0,1},
{0,1},
{0,1}
},'L',0
};
b[60]=(block){
4,2,{
{0,1},
{0,1},
{0,1},
{1,1}
},'L',1
};
for(int i=0;i<10;++i)
for(int j=0;j<=i;++j)
Id[i][j]=++tot;
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int ok=0;
for(int i=0;i<10;++i){
cin>>mp[i];
for(int j=0;j<=i;++j)
if(mp[i][j]!='.'&&!use[mp[i][j]])++ok,use[mp[i][j]]=1;
}
dfs(ok);
cout<<"No solution"<<'\n';
return 0;
}