现在手头有一批刚好能盖住2个小方格的长方形瓷砖。 瓷砖只有两种颜色：黄色和橙色。 小明想知道，对于这么简陋的原料，可以贴出多少种不同的花样来。 小明有个小小的强迫症：忍受不了任何2*2的小格子是同一种颜色。 （瓷砖不能切割，不能重叠，也不能只铺一部分。另外，只考虑组合图案，请忽略瓷砖的拼缝） 显然，对于 2*3 个小格子来说，口算都可以知道：一共10种贴法，如【p1.png所示】 但对于 3*10 的格子呢？肯定是个不小的数目，请你利用计算机的威力算出该数字。
注意：你需要提交的是一个整数，不要填写任何多余的内容（比如：说明性文字）
#include<stdio.h> #include<string.h> #include<set> #define max(a,b) (a>b?a:b) #define INF 0x3f3f3f3f using namespace std; int map[5][15]; set<int> s; bool judge() { int sum; for(int i=0;i<=1;i++) { for(int j=0;j<=8;j++) { sum = map[i][j]+map[i+1][j] + map[i][j+1] + map[i+1][j+1]; if(sum%4==0) return false; } } return true; } int getfeature() { int sum=0; for(int i=0;i<=2;i++) { for(int j=0;j<=9;j++) { sum <<= 1; sum += map[i][j]; } } return sum; } void dfs(int x,int y) { if(x==3) { if(judge()) { int feature = getfeature(); //printf("%d\n",feature); s.insert(feature); } return; } if(y==10) { dfs(x+1,0); return ; } if(map[x][y]!=-1) { dfs(x,y+1); return; }else { if(y+1<10&&(map[x][y+1]==-1)){ map[x][y] = 0; map[x][y+1] = 0; dfs(x,y+2); map[x][y] = 1; map[x][y+1] = 1; dfs(x,y+2); map[x][y] = -1; map[x][y+1] = -1; } if(x+1<3&&(map[x+1][y]==-1)) { map[x][y] = 0; map[x+1][y] = 0; dfs(x,y+1); map[x][y] = 1; map[x+1][y] = 1; dfs(x,y+1); map[x][y] = -1; map[x+1][y] = -1; } } } int main() { memset(map,-1,sizeof(map)); dfs(0,0); printf("%d",s.size()); }
