【BZOJ1814】Ural 1519 Formula 1 题解

返回首页 返回专题

题意

一个 m * n 的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数。

题解

嗯，我假设你在看这篇文章之前看过我的“插头DP 简易笔记”那篇文章

为了表达方便，下面所说的“左插头”，“上插头”，“下面”，“右边”都是针对当前考虑的格子而言的

首先，假如我们当前考虑的格子是障碍，那么当且仅当此时没有左插头与上插头时，状态可以转移，并且是原封不动地转移

然后假如我们当前考虑的格子是空地，那么分7种情况转移（请边画图边理解）：

1. 没有左插头与上插头。那么假如右边与下面都是空地，我们可以新建左插头与上插头，它们正好配对成左右括号

2. 有左插头，无上插头。那么左插头可以延续到下面或右边，括号不变，延续到右边需要移动括号位置

3. 无左插头，有上插头。那么上插头可以延续到下面或右边，括号不变，延续到下面需要移动括号位置

4. 左插头、右插头均为左括号。那么连接两个插头，括号均变成0，然后向右边找到第一个不配对的右括号，将其改为左括号

5. 左插头、右插头均为右括号。那么连接两个插头，括号均变成0，然后向左边找到第一个不配对的左括号，将其改为右括号

6. 左插头为左括号，右插头为右括号。此时不能转移状态，因为这相当于一条完整的回路已经被我们考虑完了。如果当前位置就是图中最后一个空地，那么应该更新答案

7. 左插头为右括号，右插头为左括号。那么连接两个插头，括号均变成0

行间转移直接将状态左移一个4进制位即可

#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;
const int base=219797;
int n,m,nn,mm,k=0;
bool a[15][15];
int bin[15];
int Hash[base],tot[2];
ULL state[2][base],sum[2][base],ans=0;

void push(ULL s,ULL num)
{
	int ss=s%base;
	while(Hash[ss])
	{
		if(state[k][Hash[ss]]==s)
		{
			sum[k][Hash[ss]]+=num;
			return;
		}
		ss++;if(ss==base) ss=0;
	}
	Hash[ss]=++tot[k];
	state[k][tot[k]]=s;
	sum[k][tot[k]]=num;
}

void gao(int i,int j)
{
	for(int u=1;u<=tot[k^1];u++)
	{
		ULL s=state[k^1][u],num=sum[k^1][u];
		int p=(s>>bin[j-1])&3,q=(s>>bin[j])&3;
		if(!a[i][j])
		{
			if (p==0 && q==0) push(s,num);
			continue;
		}
		if(p==0&&q==0)
		{
			if(a[i][j+1]&&a[i+1][j])
				push(s+(1<<bin[j-1])+(2<<bin[j]),num);
		}
		else if(p==0&&q>0)
		{
			if(a[i][j+1])
				push(s,num);
			if(a[i+1][j])
			{
				int tmp=s-q*(1<<bin[j]);
				tmp+=q*(1<<bin[j-1]);
				push(tmp,num);
			}
		}
		else if(p>0&&q==0)
		{
			if (a[i+1][j])
				push(s,num);
			if (a[i][j+1])
			{
				int tmp=s-p*(1<<bin[j-1]);
				tmp+=p*(1<<bin[j]);
				push(tmp,num);
			}
		}
		else if(p==1&&q==1)
		{
			int cnt=1,tmp;
			for (int v=j+1;v<=m;v++)
			{
				int ss=(s>>bin[v])&3;
				if (ss==1) cnt++;
				if (ss==2) cnt--;
				if (!cnt)
				{
					tmp=s-(1<<bin[v]);
					break;
				}
			}
			tmp-=(1<<bin[j-1])+(1<<bin[j]);
			push(tmp,num);
		}
		else if(p==2&&q==2)
		{
			int cnt=1,tmp;
			for (int v=j-2;v>=1;v--)
			{
				int ss=(s>>bin[v])&3;
				if (ss==2) cnt++;
				if (ss==1) cnt--;
				if (!cnt)
				{
					tmp=s+(1<<bin[v]);
					break;
				}
			}
			tmp-=(2<<bin[j-1])+(2<<bin[j]);
				push(tmp,num);
		}
		else if(p==2&&q==1)
			push(s-(2<<bin[j-1])-(1<<bin[j]),num);
		else{if(i==nn&&j==mm) ans+=num;}
	}
}

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();
			a[i][j]=(c=='.');
			if(a[i][j]) nn=i,mm=j;
		}
	for(int i=0;i<=13;i++) bin[i]=(i<<1);
	tot[0]=1;sum[0][1]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			k^=1;tot[k]=0;
			memset(Hash,0,sizeof(Hash));
			gao(i,j);
		}
		for(int j=1;j<=tot[k];j++)
			state[k][j]<<=2;
	}
	printf("%llu\n",ans);
	return 0;
}