插头 DP

发表于 | 分类于 | 阅读次数:
插头 DP, 全称基于连通性状态压缩的动态规划，可用于求解的问题包括但不限于棋盘上的路径问题。在算法竞赛中算是个历史悠久的知识点了，本文参照了 CDQ 神犇的论文。

方法介绍

顾名思义，基于连通性的状态压缩动态规划算法的特别之处是以动态规划算法为基本框架、以连通性为状态、以状态压缩为状态表示方法的一种算法。

仍记得那道经典题目陪伴我度过的数日时光，次次失败未曾使我放手……算了我编不下去了……

总之就是有一道经典入门题目：Formula

给定一个 $n\times m$ 的带障碍棋盘，求共有多少条回路使得经过每个非障碍格子恰好一次。

$n,m\leq12$

首先我们要明确怎么划分状态，不难想到：可以逐行、逐列、逐格，神犇证明出逐格递推最好，蒟蒻在此不再赘述。

然后就是如何表示状态的问题了；容易想到有两种状态需要表示：当前格的位置，插头的连通性状态。

位置状态没什么好说的，要说的就是连通性状态，有很多种表示方法：

最小表示法

这是一种很直观也没有什么思维难度的表示方法，缺陷就是慢，不过鉴于近年来评测机的 CPU 速度提升很大，在内存能存下的数据范围内时间消耗本身就很低，最多也就是常数翻三番，问题不大。

所谓最小表示就是将最多 $m$ 个插头划分为一些连通块，然后编号压进 long long 中，开数组肯定不行，写个哈希表即可。

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using std::cin;
using std::cout;
using std::endl;
typedef long long ll;

const int MAXN=15,MOD=(1<<15)-1,MAXST=1e6+5;

int N,M;

bool mp[MAXN][MAXN];int stt[MAXN];
int ex,ey;
struct HM
{
	int hd[MOD],nxt[MOD];
public:
	int sz;
	ll key[MAXST],val[MAXST];
	void clear(){sz=0;memset(val,0,sizeof(val));memset(hd,-1,sizeof(hd));}
	ll *find(ll k)
	{
		for(int i=hd[k&MOD];~i;i=nxt[i])
			if(key[i]==k) return &val[i];
		return NULL;
	}
	ll *alc(ll k)
	{
		key[++sz]=k,nxt[sz]=hd[k&MOD];hd[k&MOD]=sz;
		return &val[sz];
	}
	ll &operator[](const ll &k)
	{
		ll *res=find(k);
		if(res) return *res;
		else return *alc(k);
	}
} hm[2];

void dcd(ll st)//decode
{
	for(int i=M;i>=0;i--,st>>=3)
		stt[i]=st&7;
}

ll ecd()//encode
{
	static int id[MAXN];int idcnt=0;
	memset(id,-1,sizeof(id));
	id[0]=0;ll res=0;
	for(int i=0;i<=M;i++)
	{
		if(id[stt[i]]==-1) id[stt[i]]=++idcnt;
		stt[i]=id[stt[i]];
		res<<=3;res|=stt[i];
	}
	return res;
}

inline void sft(){for(int i=M;i;i--) stt[i]=stt[i-1];stt[0]=0;}//shift

ll solve()
{
	int i,j,k,u=0,v=1;ll res=0;
	hm[u].clear();hm[u][0]=1;
	for(i=1;i<=N;i++) for(j=1;j<=M;j++)
	{
		if(!(i==1&&j==1)) u^=1,v^=1;
		hm[v].clear();
		for(k=1;k<=hm[u].sz;k++)
		{
			dcd(hm[u].key[k]);
			int L=stt[j-1],U=stt[j];
			if(!mp[i][j]||(L==U&&i==ex&&j==ey))
			{
				stt[j-1]=stt[j]=0;
				if(j==M) sft();
				hm[v][ecd()]+=hm[u].val[k];
				continue;
			}
			if(L&&U)
			{
				if(L!=U)
				{
					stt[j-1]=stt[j]=0;
					for(int t=0;t<=M;t++)
						if(stt[t]==U) stt[t]=L;
					if(j==M) sft();
					hm[v][ecd()]+=hm[u].val[k];
				}
			}else if((L&&(!U))||((!L)&&U))
			{
				int t=L?L:U;
				if(mp[i][j+1])
				{
					stt[j-1]=0,stt[j]=t;
					hm[v][ecd()]+=hm[u].val[k];
				}
				if(mp[i+1][j])
				{
					stt[j-1]=t,stt[j]=0;
					if(j==M) sft();
					hm[v][ecd()]+=hm[u].val[k];
				}
			}
			else if(mp[i][j+1]&&mp[i+1][j])
			{
				stt[j-1]=stt[j]=13;
				hm[v][ecd()]+=hm[u].val[k];
			}
		}
	}
	for(i=1;i<=hm[v].sz;i++) res+=hm[v].val[i];
	return res;
}

int main()
{
	cin>>N>>M;
	int i,j;char c;
	for(i=1;i<=N;i++) for(j=1;j<=M;j++)
	{
		do c=getchar();while(c!='*'&&c!='.');
		if(c=='.') ex=i,ey=j,mp[i][j]=true;
	}
	if(ex) cout<<solve()<<endl;
	else puts("0");
	return 0;
}