俄罗斯方块

?????????????

俄罗斯方块

322D

题意：在4*4方格中分别给出3个俄罗斯方块，问是否可以经过旋转，平移操作恰好拼满整个4*4格子？ 不能重叠和越界。

输入样例：

样例解释?

思路：

首先是如何存储图形以及变化后的图形，当然不仅要方便变换还要方便最后检查。然后就想到了状态压缩，一共最多16格子，最多需要16位就行。
也就是最大用2^16-1的数字即可表示这种状态，然后对3个俄罗斯方块一一组合遍历看看能否最4*4方格进行平铺。
? ? 如何存入状态：4*4每个格子一一对应1~16的位置，有效的格子坐标转换到一维的二进制位置进行更新。（1<<?和二进制数字相或）平移操作就是把所有位置移动一下。旋转不过是对原字符串进行适当变化，然后把所有的变换后的有效状态存下来。
?? ?如何遍历结果：将3个状态数字相或，然后看是否全是1即可，判断是否等于1<<(4*4)-1就行
要注意不能有重叠：任意两个状态数字不能相与必须为0

非常好的一道状态压缩题！！！

#include <bits/stdc++.h>
using namespace std;
const int SIZE=4;
void rotate(string s[]){//旋转函数（顺时针旋转）
	char tmp[SIZE][SIZE];
	for(int i=0;i<SIZE;i++){
		for(int j=0;j<SIZE;j++){
			tmp[j][SIZE-1-i]=s[i][j];//i为0时：tmp[0,1,2][2]=s[0][0,1,2]
		}//相当于横着的变成竖着的
	}
	for(int i=0;i<SIZE;i++){
		s[i]=string (tmp[i],tmp[i]+SIZE);//string函数：从第一个字符位置开始转换，长度位SIZE
	}
}
bool valid(int x){return x>=0&&x<SIZE;}
int get(string s[],int dx,int dy){
	int ret=0;
	for(int x=0;x<SIZE;x++){
		for(int y=0;y<SIZE;y++){
			if(s[x][y]=='#'){
				int xx=x+dx,yy=y+dy;
				if(!valid(xx)||!valid(yy)){//不能越界，函数重用嘛
					return -1;
				}
				ret |=1<<(xx*4+yy);//xx*4+yy是把每个对应格子给算成数字，然后和ret或运算修改对应位置（有1出1）
			}
		}
	}
	return ret;
}
vector<int>add(){
	vector<int>ret;//用于存放状态
	string s[SIZE];
	for(int i=0;i<SIZE;i++)cin>>s[i];//输入字符阵列
	
	for(int num=0;num<4;num++){//执行四个旋转操作
		for(int dx=-3;dx<=3;dx++){//执行平移操作，要注意的是不仅要向右平移，还要向左平移
			for(int dy=-3;dy<=3;dy++){//向上和下平移
				int v=get(s,dx,dy);//用一个数字来存下次时旋转和平移后的结果（1~16个1的状态，只需要16位即可最多2^16-1）
				if(v>=0){ret.push_back(v);
				}
			}
		}
		rotate(s);//旋转一下
	}
	return ret;//返回这个俄罗斯方块对应的全部状态
}
int main(){
	vector<int>mask[3];
	for(int id=0;id<3;id++){
		mask[id]=add();//输入字符阵列，获取四个方向，所有平移结果的状态数字，存入mask中
	}
	for(int x:mask[0]){//检查所有的情况有没有能成立的
		for(int y:mask[1]){
			for(int z:mask[2]){
				if((x|y|z)+1!=(1<<SIZE*SIZE))continue;//x|y|z就可以把1的位置全部标出来（要等于2^16-1嘛）
				if(x&y)continue;
				if(x&z)continue;
				if(z&y)continue;
				cout<<"Yes\n";
				return 0;
			}
		}
	}
	cout<<"No\n";
}