这里默认各位都会轮廓线 dp。
引入
题意：给出 \(n\times m\) 的方格，有些格子不能铺线，其它格子必须铺，可以形成多个闭合回路。问有多少种铺法？
\(2\le n,m\le 12\)
考虑如果每个格子和相邻格子（包括边缘）的衔接都合法，最终一定能形成若干个闭合回路，因此我们只需要在这个条件上 dp。
设 \(f[i,j,S]\) 表示到达 \((i,j)\) 时上方的轮廓线状态是 \(S\) 的方案数。
这里，我们称轮廓线中向下的延伸和当前格子左侧向右的延伸叫作 插头。
每次填的格子有六种可能：
然后分类讨论上面和左边分别有没有插头。
-
都没有：当前格子必须往右边和下面各延伸一个插头
-
上面有：可以把上面的插头向下延伸，或者拐弯向右延伸
-
左边有：可以把左边的插头向右延伸，或者拐弯向下延伸
-
都有：把这两个插头合并
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=13;
ll t,n,m,f[maxn*maxn][1<<12][2],lim;
void ad(ll &x,const ll &y) {x+=y;}
int main(){
scanf("%lld",&t);
while(t--){
scanf("%lld%lld",&n,&m); lim=(1<<m)-1;
memset(f,0,sizeof f);
f[0][0][0]=1;
for(ll i=1;i<=n;i++){
for(ll j=1;j<=m;j++){
ll x=(i-1)*m+j, w; scanf("%lld",&w);
for(ll S=0;S<=lim;S++){
if(w){
if(S&(1<<m-1)){
ad(f[x][(S<<1)&lim|1][0],f[x-1][S][0]);
ad(f[x][(S<<1)&lim][0],f[x-1][S][1]);
if(j<m) ad(f[x][(S<<1)&lim][1],f[x-1][S][0]);
} else{
if(j<m) ad(f[x][S<<1][1],f[x-1][S][1]);
ad(f[x][S<<1|1][0],f[x-1][S][1]);
if(j<m) ad(f[x][S<<1|1][1],f[x-1][S][0]);
}
} else{
if(!(S&(1<<m-1))){
ad(f[x][S<<1][0],f[x-1][S][0]);
}
}
}
}
}
printf("%lld\n",f[n*m][0][0]);
}
return 0;
}
问题
题意：给出 \(n\times m\) 的方格，有些格子不能铺线，其它格子必须铺，形成一个闭合回路。问有多少种铺法？
\(2\le n,m\le 12\)
这和上题唯一的区别在于必须恰好形成一个闭合回路。
每次维护的 \(S\) 包括左边的插头，是一个插头集合，我们可以多加一点信息来表示所有插头的连通性情况。
具体的，用最小表示法来表示一个插头连通性状态，然后哈希映射到一个较小的整数状态上。
但是还有更好的方法。如果算上左边的插头，我们把插头集合按 \(1\sim m\)（左边的插头所处位置是一个缝隙）的位置顺序来观察，会发现他们的连通性恰好形成一个括号序列。
具体的，比如：
\[\text{（）（（）（））} \]\[\text{1 2 3 4 5 6 7 8} \]那么第 \(1\) 个和 第 \(2\) 个插头连通，第 \(3\) 个和 第 \(8\) 个插头连通，第 \(6\) 个和第 \(7\) 个插头连通。
所以我们可以用一个三进制数来表示状态，分别表示 无插头/左括号/右括号。
设 \(p_1,p_2\) 分别表示左边和上方位置的单个位置的状态，分类讨论：
-
\(p_1=p_2=0\)：我们需要新开两个插头，一个向右，一个向下。
-
\(p_1=0,p_2>0\)：此时只有上方有插头，可以继续向下延伸，也可以拐弯向右。
-
\(p_1>0,p_2=0\)：此时只有左边有插头，可以继续向右延伸，也可以拐弯向下。
-
\(p_1=p_2=1\)：两个都是“左括号”插头。合并后长这样：
会发现蓝色和绿色的右括号连通，可以视绿色的右括号为左括号。
具体的，我们向后找到匹配上插头的右括号，变为左括号。
-
\(p_1=1,p_2=2\)：由于两个插头早已连通，此时合并完后会形成一个完整的回路，判断当前格子是否为 \((n,m)\)，只有在 \((n,m)\) 时才会合并出这样一个回路
-
\(p_1=2,p_2=1\)：直接合并。
-
\(p_1=p_2=2\)：类似于 \(p_1=p_2=1\) 的情况，我们向前面找到匹配左插头的左括号，变成右括号。
然后状态数是严重不满的，我们考虑使用哈希表存下所有有用状态，或者 unordered_map。
那么现在的时间就和有用状态有关了。为了方便，可以用四进制数代替三进制数。
点击查看代码
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define mkp make_pair
#define fi first
#define se second
#define pir pair<ll,ll>
#define pb push_back
using namespace std;
const ll maxn=20, M=3e5+10;
ll n,m,z,tot[2],st[2][M],f[2][M],bit[maxn],ex,ey,ans,b[maxn][maxn];
char a[maxn][maxn];
struct hash_table{
ll hd[M],nxt[M];
void ins(ll x,ll v){
ll p=x%299993+1;
for(ll i=hd[p];i;i=nxt[i])
if(st[z][i]==x){
f[z][i]+=v; return;
}
nxt[++tot[z]]=hd[p], hd[p]=tot[z];
st[z][hd[p]]=x, f[z][hd[p]]=v;
}
void clr(){
memset(hd,0,sizeof hd);
tot[z]=0;
}
}H;
int main(){
scanf("%lld%lld",&n,&m);
for(ll i=1;i<=n;i++){
scanf("%s",a[i]+1);
for(ll j=1;j<=m;j++){
if(a[i][j]=='.') ex=i, ey=j;
b[i][j]=(a[i][j]=='.');
}
}
bit[1]=1;
for(ll i=2;i<=m+1;i++) bit[i]=bit[i-1]<<2;
H.ins(0,1);
for(ll i=1;i<=n;i++){
for(ll j=1;j<=tot[z];j++) st[z][j]<<=2;
for(ll j=1;j<=m;j++){
z^=1, H.clr();
for(ll k=1;k<=tot[z^1];k++){
ll msk=st[z^1][k], val=f[z^1][k], p1=(msk>>(j-1<<1))&3, p2=(msk>>(j<<1))&3;
if(a[i][j]=='*'){
if(!p1&&!p2) H.ins(msk,val);
} else{
if(!p1&&!p2&&b[i][j+1]&&b[i+1][j]) H.ins(msk+bit[j]+2*bit[j+1],val);
if(!p1&&p2){
if(b[i][j+1]) H.ins(msk,val);
if(b[i+1][j]) H.ins(msk-p2*bit[j+1]+p2*bit[j],val);
}
if(p1&&!p2){
if(b[i+1][j]) H.ins(msk,val);
if(b[i][j+1]) H.ins(msk-p1*bit[j]+p1*bit[j+1],val);
}
if(p1==1&&p2==1){
ll c=1;
for(ll r=j+2;r<=m+1;r++){
ll x=(msk>>(r-1<<1))&3;
if(x==1) ++c;
if(x==2) --c;
if(!c){
H.ins(msk-bit[j]-bit[j+1]-bit[r],val);
break;
}
}
}
if(p1==1&&p2==2){
if(i==ex&&j==ey) ans+=val;
}
if(p1==2&&p2==1) H.ins(msk-2*bit[j]-bit[j+1],val);
if(p1==2&&p2==2){
ll c=1;
for(ll r=j-1;r;r--){
ll x=(msk>>(r-1<<1))&3;
if(x==2) ++c;
if(x==1) --c;
if(!c){
H.ins(msk-2*(bit[j]+bit[j+1])+bit[r],val);
break;
}
}
}
}
}
}
}
printf("%lld",ans);
return 0;
}