11092: 【原1092】小F的地板

题目

题目描述

author: 寿鹤鸣 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1092

Description

小F最近购置了一幢豪宅，他家的大厅是一个M×N的矩形，现在需要在大厅中放置地板，

他找到好基友小X，小X表示他只有两类地板：

1. 2×1,1×2的矩形
2. 2×2的矩形但缺一个1×1的角

小F要求地面全部被地板覆盖且地板不能重叠，问有多少种放置方案？

Input Format

一行用空格隔开的两个整数\( M, N，(1 \leq M,N \leq 9) \) 分别表示大厅的长和宽

Output Format

一个数X表示放置方案的种数，如果没有符合要求的放置方案输出0

Sample Input 1

2 1

Sample Output 1

1

Sample Input 2

1 2

Sample Output 2

1

Sample Input 3

2 3

Sample Output 3

5

FineArtz's solution

/* 小F的地板 */
#include <iostream>
#include <cstring>
using namespace std;

unsigned long long f[10][1 << 9];
int m, n;

void dp(int lim, int col, int now, int last, int exNow, int exLast){
    if (exNow == 1 && exLast == 1){
        exNow = 0;
        exLast = 0;
        ++col;
    }
    if (col > n || (col == n && (exNow || exLast)))
        return;
    if (col == n && exNow == 0 && exLast == 0){
        f[lim][now] += f[lim - 1][last];
        return;
    }
    if (exNow == 0 && exLast == 0){
        dp(lim, col + 1, (now << 1) | 1, last << 1, 0, 0); //2 * 1
        dp(lim, col + 2, (now << 2) | 3, (last << 2) | 3, 0, 0); //1 * 2, exNow = 0
        dp(lim, col + 1, (now << 2) | 3, (last << 1) | 1, 1, 0); //1 * 2, exNow = 1
        dp(lim, col + 1, (now << 1) | 1, last << 2, 0, 1); //bottom right
        dp(lim, col + 2, (now << 2) | 2, last << 2, 0, 0); //bottom right
        dp(lim, col + 2, (now << 2) | 1, last << 2, 0, 0); //bottom left
        dp(lim, col + 1, (now << 2) | 3, last << 1, 1, 0); //top right
        dp(lim, col + 2, (now << 2) | 3, (last << 2) | 1, 0, 0); //top right
        dp(lim, col + 2, (now << 2) | 3, (last << 2) | 2, 0, 0); //top left
        //dp(lim, col, now << 1, last, 1, 0); //none, exNow = 1
        dp(lim, col + 1, now << 1, (last << 1) | 1, 0, 0); //none, exNow = 0
        //dp(lim, col, now, (last << 1) | 1, 0, 1); //none, exLast = 1
    }
    else if (exNow == 1 && exLast == 0){
        //dp(lim, col + 2, (now << 1) | 1, (last << 2) | 2, 0, 0); //2 * 1
        dp(lim, col + 2, (now << 1) | 1, last << 2, 0, 0); //bottom left
    }
    else{
        dp(lim, col + 1, (now << 2) | 3, last, 1, 0); //1 * 2
        dp(lim, col + 2, (now << 2) | 3, (last << 1) | 1, 0, 0); //1 * 2
        dp(lim, col + 2, (now << 2) | 3, last << 1, 0, 0); //top left
        //dp(lim, col + 2, (now << 2) | 1, last << 1, 0, 0); //2 * 1
    }
}

int main(){
    cin >> m >> n;
    if (m > n)
        m ^= n ^= m ^= n;
    memset(f, 0, sizeof(f));
    f[0][(1 << n) - 1] = 1;
    for (int i = 1; i <= m; ++i)
        dp(i, 0, 0, 0, 0, 0);
    cout << f[m][(1 << n) - 1] << endl;
    return 0;
}