本篇通過(guò)圖文解析講述插頭DP的內(nèi)容，結(jié)合前面的狀態(tài)壓縮DP知識(shí)，以及前置知識(shí)：哈希，方便大家能快速理解。

在闡述什么是插頭DP之前，我們先了解插頭DP有什么用？插頭DP是用來(lái)解決一類網(wǎng)格圖上的連通性問(wèn)題的強(qiáng)力工具。題目的特征是給定的網(wǎng)格非常?。ㄟ@個(gè)特征類似狀壓DP）。事實(shí)上，插頭DP也可以看做是狀壓DP的一種。

一、什么是插頭DP

很顯然，是一個(gè)關(guān)于插頭的動(dòng)態(tài)規(guī)劃。那么，什么是插頭呢？

如圖我們?cè)谝粋€(gè)方格內(nèi)，關(guān)于格點(diǎn)畫一條閉合回路。

對(duì)于每一個(gè)方格，內(nèi)部，有六種情況

不難發(fā)現(xiàn)，對(duì)于回路里的任何一個(gè)方格，四條邊中，有且僅有兩個(gè)與表示路徑的藍(lán)色線相交。這也很好理解，進(jìn)一次，出一次，C（4，2）=6。

我們現(xiàn)在把格子里的藍(lán)色線條，變成從格子中心指向外邊的→。

這個(gè)箭頭，也就是所謂的插頭。

二、例題

我們結(jié)合一個(gè)例題來(lái)看。

題目：給出n*m的方格，有些格子不能鋪線，其它格子必須鋪，可以形成多個(gè)閉合回路。問(wèn)有多少種鋪法？

輸入格式

每個(gè)測(cè)試點(diǎn)多組數(shù)據(jù)

第一行一個(gè)正整數(shù)T，表示有T組數(shù)據(jù)

每組數(shù)據(jù)：

第1行，n,m(2<=n,m<=12)

從第2行到第n+1行，每行m個(gè)數(shù)字（1 or 0），1表鋪線，0表不鋪線

輸出格式

每組數(shù)據(jù)輸出一個(gè)整數(shù)（表方案數(shù)）

輸入輸出樣例

題目大意：給出n*m的方格，有些格子不能鋪線，其它格子必須鋪，可以形成多個(gè)閉合回路。問(wèn)有多少種鋪法？（1<=n,m<=12)

那么，把回路模型變成插頭模型有什么好處或者性質(zhì)呢？

1. 首先，我們可以發(fā)現(xiàn)，如果一個(gè)格子上方的格子有下插頭，那這個(gè)格子一定有上插頭。其它方向類似。

2. 按1的方法設(shè)置插頭，最后一定會(huì)構(gòu)成回路。

3. 一個(gè)格子的合理取法合且僅合相鄰的格子有關(guān)。

觀察下第三點(diǎn)，它其實(shí)代表了無(wú)后效性。假設(shè)我們從上到下，從左到右的處理每一個(gè)格子，那么我們只需要記錄部分格子的狀態(tài)即可，再往上的格子具體狀態(tài)不用知道。

如上圖，對(duì)于當(dāng)前格子，我們只需要知道紅色的這些格子就行了，再上面的格子具體的取法，已經(jīng)不會(huì)對(duì)下面任何未處理的格子產(chǎn)生影響。

已經(jīng)掌握了狀態(tài)壓縮的你，一定能輕松的算出狀態(tài)總數(shù)，每個(gè)格子6種，維護(hù)n個(gè)格子?？偣?img src="/assets/addons/ueditor/php/upload/image/20221115/1668486866465886.png" title="6n" alt="6n" width="19" height="25"/>種狀態(tài)，只有2e9個(gè)狀態(tài)。

別急，我們真的需要2e9個(gè)狀態(tài)嘛？這些格子里，指向彼此和已經(jīng)處理過(guò)的格子的插頭，顯然是廢物信息。我們實(shí)際上只需要知道這些插頭嘛：

藍(lán)色的是其它格子需要用到的，黃色的是當(dāng)前格子需要用到的。我們叫紅色的這個(gè)線為輪廓線。我們只需要知道這輪廓線上m+1個(gè)箭頭是否存在就可以了?？偣?img src="/assets/addons/ueditor/php/upload/image/20221115/1668484896962789.png" title="狀態(tài)" alt="狀態(tài)" width="54" height="21"/>個(gè)狀態(tài)。再乘上n和m，時(shí)空復(fù)雜度都綽綽有余。

那么，怎么實(shí)現(xiàn)呢？我們要解決兩個(gè)問(wèn)題。

1. 已知這些插頭的情況下，這個(gè)方格該如何填。

2. 填完這個(gè)方格后，如何得到下一個(gè)方格所需要的插頭狀態(tài)，更特殊的，如何從上一行行末，變到下一行行初。

問(wèn)題1：

0：若這個(gè)格子不能走，則不能存在左側(cè)和上方插頭。

1：如果當(dāng)前格子存在左側(cè)插頭和上方插頭，那么只有一種合理填法。

2：如果僅存在左側(cè)插頭，那么有兩種合理填法。

3：如果僅存在上方插頭，那和上一種類似，也是兩種填法。

4：如果都不存在呢？只有一種填法

問(wèn)題2：

解答了問(wèn)題1，顯然我們也得到了問(wèn)題2的解答，畢竟我們填出了這個(gè)格子，自然知道插頭分布。唯一特殊的是上一行末到這一行頭的處理。上一行末不可能有右插頭，那我們直接把上一行末狀態(tài)的表示最后是否存在右插頭的位置去掉，再添加一個(gè)表示沒(méi)有左插頭的位，不就表示出了這一行第一個(gè)的狀態(tài)了嘛，為了方便寫，下方的代碼里，用dp[i][0][mask]表示轉(zhuǎn)移后的上一行行末狀態(tài)。

到這里，我們已經(jīng)得到了解法了，成熟的評(píng)測(cè)機(jī)，應(yīng)該自動(dòng)AC了吧（劃去）。

代碼如下：

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;
int n,m,maxk,a[13][13];
long long dp[13][13][1<<14];
void init()
{ 
	scanf("%d%d",&n,&m);
	maxk=(1<<(m+1))-1;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	memset(dp,0,sizeof(dp));
}
void solve()
{
	int prei,prej;
	dp[0][m][0]=1;
	for (int i=1;i<=n;i++)
	{
		for (int k=0;k<=maxk;k++)
		{
			dp[i][0][k<<1]=dp[i-1][m][k];
		}
		for (int j=1;j<=m;j++)
		{
			prei=i;
			prej=j-1;
			for (int k=0;k<=maxk;k++)
			{
				int b1=(k>>(j-1))&1;
				int b2=(k>>j)&1;
				if (!a[i][j])
				{
					if (!b1&&!b2) dp[i][j][k]+=dp[prei][prej][k];
				}
				else if (!b1&&!b2)
				{
					dp[i][j][k+(1<<j)+(1<<(j-1))]+=dp[prei][prej][k];
				}
				else if (b1&&!b2)
				{
					dp[i][j][k]+=dp[prei][prej][k];
					dp[i][j][k+(1<<(j-1))]+=dp[prei][prej][k];
				}
				else if (!b1&&b2)
				{
					dp[i][j][k]+=dp[prei][prej][k];
					dp[i][j][k-(1<<(j-1))]+=dp[prei][prej][k];
				}
				else if (b1&&b2)
				{
					dp[i][j][k-(1<<j)-(1<<(j-1))]+=dp[prei][prej][k];
				}
			}
		}
	}
	printf("%lld\n",dp[n][m][0]);
}
int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		init();
		solve();
	}
	return 0;
}