【luogu P5056】【模板】插头dp（插头DP）（分类讨论）

【模板】插头dp

题目链接：luogu P5056

题目大意

有一个 n*m 的网格，每个格子要么必须铺线，要么必须不铺。
然后问你有多少个铺发使得形成一个闭合回路。

思路

快乐插头 DP 模板题。

首先默认都会插头 DP，其实不会也没啥，其实就是你压你当前处理的位置跟没处理的分界线（一般叫轮廓线）。
所以主要的问题是如何压状态，因为似乎直接用这个位置是否有线不太能表示出对于的状态，它们之间还有连通关系。

那考虑是怎样连通的，自然是两两对着的，而且因为是闭合回路，自然是不会出现交叉的，所以有一个东西叫做括号序列就跟这个东西对应上了。
然后你就把左括号变成 $1$，右括号变成 $2$，如果是不铺的就是 $0$。
然后为了快速以及方便其实我们可以把它弄成 $2^2=4$ 进制的。

于是我们考虑分类的讨论：
首先不能铺的格子就不铺啊，那就必须是 $00$，下面默认能铺。

$00$：就只能右跟下，因为一定要铺，所以变成了 $12$。
$01$：那就续上这条线段，续到右边 $01$ 或者下面 $10$ 都行。
自然 $02,10,20$ 同理，就是续。
$11$：看起来一定要接上，但是又不能接上，似乎矛盾了。于是考虑把后面那个改成 $2$，这样不会重复因为这个 $2$ 只有这样才会诞生。那这个改成 $2$ 你就相当于把后面的 $1$ 对于的 $2$ 去掉变成 $0$，这个你直接往后扫 $O(n)$ 找没问题的。
$22$：跟 $11$ 一样的道理，不过这次你是找前面跟第一个 $2$ 匹配的 $1$ 把它变成 $0$。
$21$：这个就直接接上，变成 $00$ 即可。
$12$：这个就是最后一步把环合上，自然只能在最后一个点出现，在这里统计入答案即可。

然后是一些注意事项：

1. 这个最后一步不一定是右下方，因为可能那里不能铺，要找的是最后一个能铺的位置。
2. 自然要滚动数组，毕竟状态数不少。
3. 发现直接搞状态时还是太多了，但是插头 DP 特有的有用状态少使得我们可以试着只把有用的状态找出来。
   但是你怎么对应上呢？那就用哈希吧！
   不过感觉这里邻接表样子的哈希不如往后移找位置的。（个人感觉，所以写的是后者）
4. 注意换到新的一行，轮廓写一列的那个位置从最后变回到了最前，记得把之前的状态改一下。
   因为我这里状态是按顺序压的，当然你也可以把特殊的那个一列的轮廓一直放在 $0$ 的位置也不是不行。

代码

#include
#include 
#define ll long long
#define ull unsigned long long

using namespace std;

const int N = 13;
const int S = 1e5 + 100;
const int HS = 100003;
int n, m, tot[2], _, hash[HS], ex, ey;
bool in[N][N];
ll f[2][S], fv[2][S], ans;

void add(ll S, ll va) {
	int x = S % HS;
	while (hash[x]) {
		if (fv[_][hash[x]] == S) {
			f[_][hash[x]] += va; return ;
		}
		x = (x + 1) % HS;
	}
	hash[x] = ++tot[_]; fv[_][hash[x]] = S; f[_][hash[x]] = va;
}

int main() {
	scanf("%d %d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			char c = getchar(); while (c != '*' && c != '.') c = getchar();
			if (c == '.') in[i][j] = 1, ex = i, ey = j;
		}
	
	tot[0] = 1; f[0][1] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			_ ^= 1;
			tot[_] = 0; memset(hash, 0, sizeof(hash));
			for (int k = 1; k <= tot[_ ^ 1]; k++) {
				ll S = fv[_ ^ 1][k];
				ll l = (S >> ((j - 1) << 1)) & 3;
				ll r = (S >> (j << 1)) & 3;
				if (!in[i][j]) {
					if (!l && !r) add(S, f[_ ^ 1][k]);
					continue;
				}
				if (!l && !r) {
					if (!in[i][j + 1] || !in[i + 1][j]) continue;
					add(S ^ (1 << ((j - 1) << 1)) ^ (2 << (j << 1)), f[_ ^ 1][k]);
				}
				if (!l && r) {
					if (in[i + 1][j]) add(S ^ (r << (j << 1)) ^ (r << ((j - 1) << 1)), f[_ ^ 1][k]);
					if (in[i][j + 1]) add(S, f[_ ^ 1][k]);
				}
				if (l && !r) {
					if (in[i + 1][j]) add(S, f[_ ^ 1][k]);
					if (in[i][j + 1]) add(S ^ (l << ((j - 1) << 1)) ^ (l << (j << 1)), f[_ ^ 1][k]);
				}
				if (l == 1 && r == 1) {
					int num = 0;
					for (int o = j + 1; o <= m; o++) {
						if (((S >> (o << 1)) & 3) == 1) num++;
							else if (((S >> (o << 1)) & 3) == 2) num--;
						if (num < 0) {
							add(S ^ (1 << ((j - 1) << 1)) ^ (1 << (j << 1)) ^ (2 << (o << 1)) ^ (1 << (o << 1)), f[_ ^ 1][k]);
							break;
						}
//						if (o == m) {
//							while (1) {
//								ans++;
//							}
//						}
					}
				}
				if (l == 2 && r == 2) {
					int num = 0;
					for (int o = j - 2; o >= 0; o--) {
						if (((S >> (o << 1)) & 3) == 1) num--;
							else if (((S >> (o << 1)) & 3) == 2) num++;
						if (num < 0) {
							add(S ^ (2 << ((j - 1) << 1)) ^ (2 << (j << 1)) ^ (1 << (o << 1)) ^ (2 << (o << 1)), f[_ ^ 1][k]);
							break;
						}
//						if (o == 0) {
//							while (1) {
//								ans++;
//							}
//						}
					}
				}
				if (l == 2 && r == 1) {
					add(S ^ (2 << ((j - 1) << 1)) ^ (1 << (j << 1)), f[_ ^ 1][k]);
				}
				if (l == 1 && r == 2) {
					if (i == ex && j == ey) ans += f[_ ^ 1][k];
				}
			}
		}
		for (int j = 1; j <= tot[_]; j++) fv[_][j] <<= 2;//把跑到最右边的状态移会最左边 
	}
	
	printf("%lld", ans);
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105