有2种不同颜色规格为1*2的瓷砖，用其来铺设地板，不能重叠和越界。并且，地板中任意2*2的格子不能为同一种颜色。如图，当地板为2*3时，有10种铺设方案。问：当地板为3*10时，问有多少种铺设方案？
dfs深搜
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; #define maxn 3 #define maxm 10 int a[maxn][maxm]; int ans; bool check() { for(int i = 0; i < maxn-1; i++) for(int j = 0; j < maxm-1; j++) { int p = a[i][j]; if(p == -1) return false; //地板必须全部铺满 if(p == a[i+1][j] && p == a[i][j+1] && p == a[i+1][j+1]) return false; //任意2*2格子不能为同一种颜色 } return true; } void dfs(int cur) { if(cur == maxn * maxm) { if(check()) { ans++; } return; } //计算出 int x = (cur - 1) / maxm; int y = cur - x * maxm - 1; if(a[x][y] != -1)dfs(cur + 1);//格子已经铺了 //横着铺 if(y + 1 < maxm && a[x][y] == -1 && a[x][y + 1] == -1) { a[x][y] = a[x][y + 1] = 0; dfs(cur + 1); a[x][y] = a[x][y + 1] = 1; dfs(cur + 1); a[x][y] = a[x][y + 1] = -1; } //竖着铺 if(x + 1 < maxn && a[x][y] == -1 && a[x + 1][y] == -1) { a[x][y] = a[x + 1][y] = 0; dfs(cur + 1); a[x][y] = a[x + 1][y] = 1; dfs(cur + 1); a[x][y] = a[x + 1][y] = -1; } } int main() { memset(a,-1,sizeof(a)); ans = 0; dfs(1); cout<<ans<<endl; return 0; }
