11383: 【原1383】畅畅的牙签袋

题目描述

author: SamJia 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1383

题目描述

畅畅说：“你们都说窝脑子瓦特了，我看你们才是脑子瓦特嘞- -”

为了阻挠我们再次揭露他的无chǐ，畅畅妄图破坏我们的显示器，他拿出了自己收集的牙签包装袋，其大小是1×2的矩形，他想用密铺的方式把显示器全部遮挡住。显示器大小是W×H的矩形，畅畅把包装袋背面涂上了胶水，开始一块一块粘到显示器上，要求不能有包装袋重叠，也不能有显示器的某一部分没被遮挡，包装袋的放置只有两种情况：横放和竖放。

畅畅为自己的周密计划洋洋得意之时，脑子又瓦特了，他想让你帮他算算针对每台显示器一共有多少种不同的密铺方式。

说明

认为显示器是有方向的，即对称的密铺方式要算重复计数，例如 2×2 的显示器密铺方案有两种，一种是2个包装袋都横放，另一种是两个包装袋都竖放。
不能密铺的则输出0。
牙签包装袋足够用。

输入格式

输入包括若干行，每行有两个整数Wi和Hi，表示这台显示器大小，输入数据以Wi=Hi=0作为结束，每台显示器大小 1<=Hi,Wi<=11。

输出格式

针对每行输入，每次输出一个整数表示对该显示器密铺的方案总数。Wi=Hi=0时不需要输出。

Sample Input

Sample Output

提示

畅畅说如果Wi×Hi是奇数的话可行的方案数就是0了。

畅畅思来想去，认为以行为单位来一行行填充，同时用状态压缩的方式表示每一行的填充状态，0表示空1表示已填充，如一个长为3的行有000，001，010，011，100，101，110，111这样几种状态表示。

畅畅觉得动态规划太难的话，只有暴力搜索了。

畅畅说30%测试点只有一台显示器，70%测试点只有不超过十台显示器，100%测试点只有不超过121台显示器

畅畅说答案很小的，long long就够了

yyong119's solution

#include <iostream>
#include <cstring>
using namespace std;

int W, H;
long long cnt = 1;
long long dp[12][1 << 12];

void findall(int line, int state, int pos) {

    if (pos == W) {
        dp[line][state] += cnt;
        return;
    }
    findall(line, state, pos + 1);//Leave this position empty
    if (pos <= W - 2 && !(state & (1 << pos)) && !(state & (1 << (pos + 1)))) {//Fill two horizontal positions
        int next = state | (1 << pos) | (1 << (pos + 1));
        findall(line, next, pos + 2);
    }
}

int main() {

    while (cin >> W >> H && W != 0) {

        if (W > H) { int tmp = W; W = H; H = tmp; }
        if (W * H % 2 == 1) {
            cout << 0 << endl; continue;
        }
        memset(dp, 0, sizeof(dp));
        cnt = 1;

        findall(1, 0, 0);
        for (int i = 2; i <= H; ++i)
            for (int j = 0; j < (1 << W); ++j) {
                if (dp[i - 1][j]) cnt = dp[i - 1][j];
                    else continue;
                findall(i, (~j) & ((1 << W) - 1), 0);
            }

        cout << dp[H][((1 << W) - 1)] << endl;
    }
    return 0;
}