題目大意:要在n * m的網格上面鋪滿1 * 2或者 2 * 1的磚塊,問有多少種鋪放的方式
解題思路:剛開始用了3進制表示每行的狀態,0表示的是2 * 1的磚塊的一部分,1表示的是1 * 2的磚塊的上部分,2表示的是1 * 2的磚塊的下部分,然後像poj-1185炮兵陣地 那題一樣去解決就好了,結果發現狀態太多了,會TLE,只得放棄了
後面參考了下別人的代碼,可以將其轉換成二進制表示形式的,0代表沒該位置沒被鋪到,1代表該位置有被鋪到
因為有1 * 2的這種影響兩行的磚頭存在,所以要判斷兩個狀態能否吻合,只有吻合了才可以
分類討論
1.如果第i行的第j列是1
A.如果第i-1行的第j列也是1,那麼這裡鋪的磚就不可能是1*2這種類型的磚(影響2行的磚),也就是他們兩個鋪的都是2*1的磚,那就要判斷其相鄰的那個是不是也是1了,如果不是,就表示兩種狀態不吻合了
B.如果第i-1行的第j列是0,那麼表示第i行第j列的磚是1 * 2的磚,上部分將第i-1行的第j列給鋪了
2.如果第i行的第j列是0
A.如果第i-1行的第j列也是0,那麼就出現空缺了,不符合
B.如果第i-1行的第j列是1,就表示第i行需要第i+1行鋪1 *2的磚來填補了
可參考大神的題解這裡寫鏈接內容
A的代碼
#include
#include
#include
using namespace std;
#define maxn 15
#define maxs (1 << 12)
long long ans[maxn][maxn];
long long dp[maxn][maxs];
int h, m;
bool ok(int s) {
for(int i = m - 1; i >= 0; i--) {
if(s & (1 << i)) {
if(i == 0)
return false;
if(!(s & (1 << (i - 1))))
return false;
i--;
}
}
return true;
}
bool judge(int s, int ss) {
for(int i = (m - 1); i >= 0; i--) {
if(!(ss & (1 << i)) && !(s & (1 << i)))
return false;
if((s & (1 << i))) {
if(ss & (1 << i)) {
if(i == 0)
return false;
if(!(s & (1 << (i - 1))) || !(ss & (1 << (i - 1))))
return false;
i--;
}
}
}
return true;
}
void solve() {
int t;
if(h < m) {
t = h;
h = m;
m = t;
}
memset(dp, 0, sizeof(dp));
for(int i = 0; i < (1 << m); i++)
if(ok(i))
dp[1][i] = 1;
for(int r = 2; r <= h; r++)
for(int s = 0; s < (1 << m); s++)
for(int ss = 0; ss < (1 << m); ss++)
if(judge(s, ss))
dp[r][s] += dp[r-1][ss];
printf(%lld
, ans[h][m] = ans[m][h] = dp[h][(1 << m) - 1]);
}
int main() {
memset(ans, -1, sizeof(ans));
while(scanf(%d%d, &h, &m) != EOF && h + m) {
if(ans[h][m] != -1) {
printf(%lld
, ans[h][m]);
continue;
}
if((h * m) % 2 == 1) {
ans[h][m] = ans[m][h] = 0;
printf(0
);
continue;
}
solve();
}
return 0;
}
三進制超時的代碼
#include
#include
#include
#include
using namespace std;
#define maxn 270000
int state[maxn];
int dp[12][maxn];
int w, h, cnt;
int mod[13];
void init() {
memset(dp, 0, sizeof(dp));
cnt = 0;
bool flag1, flag2;
for(int i = 0; i < mod[w]; i++) {
flag1 = flag2 = false;
for(int j = w - 1; j >= 0; j--) {
if((i % mod[j + 1] - i % mod[j]) / mod[j] == 0) {
if(j == 0) {
flag1 = true;
break;
}else {
if((i % mod[j] - i % mod[j - 1]) / mod[j - 1] != 0) {
flag1 = true;
break;
}
}
j--;
}
}
if(!flag1) {
for(int j = w - 1; j >= 0; j--) {
if((i % mod[j + 1] - i % mod[j]) / mod[j] == 2) {
flag2 = true;
break;
}
}
}
if(!flag1)
state[cnt++] = i;
if(!flag1 && !flag2)
dp[0][i] = 1;
}
}
int solve() {
for(int r = 1; r < h; r++)
for(int i = 0; i < cnt; i++)
for(int j = 0; j < cnt; j++) {
bool flag = false;
for(int k = w - 1; k >= 0; k--) {
if(((state[j] % mod[k + 1] - state[j] % mod[k] ) / mod[k] == 1) && ( (state[i] % mod[k + 1] - state[i] % mod[k] ) / mod[k] != 2)) {
flag = true;
break;
}
if(((state[i] % mod[k + 1] - state[i] % mod[k] ) / mod[k] == 2) && ( (state[j] % mod[k + 1] - state[j] % mod[k] ) / mod[k] != 1)) {
flag = true;
break;
}
}
if(!flag) {
dp[r][state[i]] += dp[r-1][state[j]];
}
}
int ans = 0;
for(int i = 0; i < cnt; i++) {
bool flag = false;
for(int j = w - 1; j >= 0; j--)
if((state[i] % mod[j + 1] - state[i] % mod[j]) / mod[j] == 1) {
flag = true;
break;
}
if(!flag) {
ans += dp[h - 1][state[i]];
}
}
return ans;
}
void begin() {
mod[0] = 1;
for(int i = 1; i < 13; i++)
mod[i] = mod[i - 1] * 3;
}
int main() {
begin();
while(scanf(%d%d, &h, &w) != EOF && h + w) {
if((h * w) % 2 == 1)
printf(0
);
else {
init();
printf(%d
, solve());
}
}
return 0;
}