bzoj5156 [Tjoi2014]拼图

bzoj5156 [Tjoi2014]拼图

​​ Description

小Z最近迷上了拼图游戏，然而智商有限，他总是无法拼出完整图案。游戏是这样的：首先小Z会得到一些拼图碎片 ，然后他试着重新排列这些碎片使得它们组成一个大小为4*4的正方形。如下图。注意小Z不能旋转或者翻转这些碎 片。

小Z得到如图1的碎片，然后经过重新排列得到图2的正方形。由于小Z实在太笨了，聪明的你请写一个程序帮助他来 解决这个问题吧。

Input

输入包含多组数据，请使用EOF。 每组数据的的第一行包含一个正整数N，表示碎片的个数。 接下来输入N个碎片。每个碎片的第一行是两个正整数r和c，表示这个碎片的行数和列数。 接下来是r行，每一行包含c个字符’0’或’1’ ’1’表示碎片占据这个位置，’0’表示该位置为空。 数据保证每个碎片都是完整的一片(即’1’是相互连通的)，并且没有行或者列全部为’0’。 N<=16

Output

如果无法组成一个正方形，输出”No Solution”； 如果有多组解，输出”Yes,many!”。否则，输出”Yes, only one!” 接下来输出一个 4 * 4 的矩阵 H，Hij表示位置 i, j 的碎片编号。碎片编号从 1 开始 Sample Input

4 2 3 111 101 4 2 01 01 11 01 2 1 1 1 3 2 10 10 11 4 1 4 1111 1 4 1111 1 4 1111 1 4 1111 Sample Output

Yes, only one! 1112 1412 3422 3442 Yes, many! HINT

Source

被自己sb剪枝wa了两个小时 tmd!

因为要求每个都必须出现所以非常容易就枚举状态暴力搜索即可

#include#include#includeusing namespace std;const int N=20;bool p[N][5][5];int ans,T,n,m,st[N][3],_ans[5][5],mp[5][5];char s[5];inline bool check(){ for (int i=1;i<=4;++i) for (int j=1;j<=4;++j) if (!mp[i][j]) return 0; return 1;}inline void dfs(int now){ if (ans>=2) return; if (now>T){if (!check())return;++ans;memcpy(_ans,mp,sizeof(mp));return;} for (int ii=st[now][1];ii<=4;++ii){ for (int jj=st[now][2];jj<=4;++jj){ bool flag=0;int x=0,y=0; for (int i=ii-st[now][1]+1;i<=ii;++i){y=0;++x; for (int j=jj-st[now][2]+1;j<=jj;++j){++y; if (p[now][x][y]&&mp[i][j]) {flag=1;break;} } if(flag) break; }if (flag) continue;x=0;y=0; for (int i=ii-st[now][1]+1;i<=ii;++i){++x;y=0; for (int j=jj-st[now][2]+1;j<=jj;++j){++y; if (p[now][x][y]) mp[i][j]=now; } } dfs(now+1);x=0;y=0; for (int i=ii-st[now][1]+1;i<=ii;++i){++x;y=0; for (int j=jj-st[now][2]+1;j<=jj;++j){++y; if (p[now][x][y]) mp[i][j]=0; } }if(ans>=2) break; }if(ans>=2) break; }}int main(){ freopen("bzoj5156.in","r",stdin); while(~scanf("%d",&T)){ memset(mp,0,sizeof(mp));ans=0;memset(p,0,sizeof(p)); for (int owo=1;owo<=T;++owo){ scanf("%d%d",&st[owo][1],&st[owo][2]); for (int i=1;i<=st[owo][1];++i){ scanf("%s",s+1); for (int j=1;j<=st[owo][2];++j) p[owo][i][j]=s[j]-'0'; } }dfs(1); if(!ans) {puts("No solution");continue;} if (ans==1){ puts("Yes, only one!"); for (int i=1;i<=4;++i) { for (int j=1;j<=4;++j) printf("%d",_ans[i][j]); puts(""); }continue; }puts("Yes, many!"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。