【模板】插头 DP

信息

此题目来自 洛谷， 原始题目与提交代码请前往 P5056 【模板】插头 DP - 洛谷。

题目背景

ural 1519

陈丹琦《基于连通性状态压缩的动态规划问题》中的例题。

题目描述

给出 ${n}\times{m}$ 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？

输入格式

第一行，两个整数，分别代表 $n,m$。

从第二行到第 $(n+1)$ 行，每行有一个长度为 $m$ 的只含 * 和 . 的字符串，* 表不能铺线，. 表必须铺。

输出格式

输出一行一个整数，表示总方案数。

输入输出样例

输入 #1

4 4
**..
....
....
....

输出 #1

2

输入 #2

4 4
....
....
....
....

输出 #2

6

说明/提示

数据规模与约定

• 对于 $100\%$ 的数据，保证 ${2}\le{n},{m}\le{12}$。

【题目来源】

NOIP 2002 普及组第四题

题目解答

注意

本题题解尚未完成/尚未完善， 不足以 AC 通过评判。

C++

/**
 * 洛谷 P5056 解答程序。
 * @author CoolCLK
 */
#include <iostream>
#include <vector>
#define repeat(n) for (size_t _= 0; _ < n; _++)
typedef unsigned int u_int;
using namespace std;

u_int n, m;
vector<vector<bool>> able;

int main() {
    cin >> n >> m;
    repeat (n) {
        able.emplace_back();
        repeat (m) {
            char c;
            cin >> c;
            switch (c) {
            case '*':
                able.back().emplace_back(false);
                break;
            case '.':
                able.back().emplace_back(true);
                break;
            default:
                break;
            }
        }
    }

    
    return 0;
}