题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1519
题目分类：插头dp
题意：求经过所有可行点的哈密顿回路的个数 * 不可走 . 可以走 2 ≤ N, M ≤ 12
代码：
括号匹配法,转移有点复杂,但是时间空间比较小
#include<bits/stdc++.h> #define LL long long
using namespace std;
const int maxn=;
int n,m,now,pre;
int mov[]={,,,,,,,,,,,,};//根据进制选择移位距离
char gp[][],fx,fy;//存图,最后一个可行点的坐标
inline int getbit(LL st,int k){ return (st>>mov[k])&;}//获得第k位的状态
inline int pybit(LL st,int k){ return st<<mov[k];} //平移k位
inline LL clrbit(LL st,int i,int j){ return st&(~(<<mov[i]))&(~(<<mov[j]));}//清空第i位和第j位
struct node//状态离散hash
{
int head[maxn],next[maxn],size;
LL sum[maxn],sta[maxn];//保存所求和及状态
void clear()
{
memset(head,-,sizeof(head));
memset(sum,,sizeof(sum));
size=;
}
void push(LL st,const LL v)
{
LL hash=st%maxn;
for(int i=head[hash];i>=;i=next[i])
{
if(sta[i]==st)
{
sum[i]+=v;
return;
}
}
sta[size]=st,sum[size]=v;
next[size]=head[hash],head[hash]=size++;
}
}dp[];
inline int fl(LL st,int pos)//从左往右找到和当前pos位置匹配的右括号
{
int cnt=;
for(int i=pos+;i<=m;i++)
{
int k=getbit(st,i);
if(k==) cnt++;
else if(k==) cnt--;
if(!cnt) return i;
}
}
inline int fr(LL st,int pos)//从右往左找到和当前pos位置匹配的左括号
{
int cnt=;
for(int i=pos-;i>=;i--)
{
int k=getbit(st,i);
if(k==) cnt++;
else if(k==) cnt--;
if(!cnt) return i;
}
}
void DP(int x,int y,int k)//每种状态的转移,根据需要修改
{
int l=getbit(dp[pre].sta[k],y-);
int up=getbit(dp[pre].sta[k],y);
LL st=clrbit(dp[pre].sta[k],y-,y);
LL v=dp[pre].sum[k];
if(!l&&!up)
{
if(gp[x][y]=='*')
{
dp[now].push(st,v);
return;
}
if(x<n&&y<m&&gp[x+][y]=='.'&&gp[x][y+]=='.')
dp[now].push(st|pybit(,y-)|pybit(,y),v);
}
else if(!l||!up)
{
int e=l+up;
if(x<n&&gp[x+][y]=='.')
dp[now].push(st|pybit(e,y-),v);
if(y<m&&gp[x][y+]=='.')
dp[now].push(st|pybit(e,y),v);
}
else if(l==&&up==)
dp[now].push(st^pybit(,fl(st,y)),v);
else if(l==&&up==)
dp[now].push(st^pybit(,fr(st,y-)),v);
else if(l==&&up==)
dp[now].push(st,v);
else if(x==fx&&y==fy)
dp[now].push(st,v);
}
LL solve()
{
dp[].clear();//初状态
dp[].push(,);
now=,pre=;
for(int i=;i<=n;i++)//逐格逐状态枚举
{
pre=now,now^=,dp[now].clear();
for(int k=;k<dp[pre].size;k++)//轮廓线下移对齐
dp[now].push(pybit(dp[pre].sta[k],),dp[pre].sum[k]);
for(int j=;j<=m;j++)
{
pre=now,now^=,dp[now].clear();
for(int k=;k<dp[pre].size;k++)
{
DP(i,j,k);
}
}
}
for(int i=;i<dp[now].size;i++)//寻找最终答案
if(dp[now].sta[i]==)
return dp[now].sum[i];
return ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<=n;i++)//都是从1开始的
scanf("%s",&gp[i][]);
fx=;
for(int i=n;i>&&!fx;i--)//寻找最后一个可行点
{
for(int j=m;j>&&!fx;j--)
{
if(gp[i][j]=='.')
fx=i,fy=j;
}
}
if(fx==) puts("");
else cout<<solve()<<endl;
}
return ;
}
最小表示法，转移简单，时间空间较大
#include<bits/stdc++.h> #define LL long long
using namespace std;
const int maxn=,inc=,bit=;//3位二进制以及111的表示
int n,m,now,pre,code[],bin[],res[];//用来表示状态的每一位的数值
char gp[][],fx,fy;//图和最后的可行点
struct node//离散化hash
{
int head[maxn],next[maxn],size;
LL sum[maxn],sta[maxn];
void clear()
{
memset(head,-,sizeof(head));
size=;
}
void push(LL st,const LL v)
{
LL hash=st%maxn;
for(int i=head[hash];i>=;i=next[i])
{
if(sta[i]==st)
{
sum[i]+=v;
return ;
}
}
sta[size]=st,sum[size]=v;
next[size]=head[hash],head[hash]=size++;
}
}dp[];
inline LL encode(int m)//将code转换成状态
{
LL st=;
int cnt=;
memset(bin,-,sizeof(bin));
bin[]=;
for(int i=m;i>=;i--)
{
if(bin[code[i]]==-)
bin[code[i]]=cnt++;
code[i]=bin[code[i]];
st<<=inc;
st|=code[i];
}
return st;
}
inline void decode(LL st,int m)//将状态转换成code
{
for(int i=;i<=m;i++)
{
code[i]=st&bit;
st>>=inc;
}
}
void DP(int x,int y,int k)//dp具体情况具体分析
{
decode(dp[pre].sta[k],m);
int l=code[y-];
int up=code[y];
code[y-]=code[y]=;
memcpy(res,code,sizeof(code));
LL v=dp[pre].sum[k];
if(!l&&!up)
{
if(gp[x][y]=='*')
dp[now].push(encode(m),v);
else if(x<n&&y<m&&gp[x+][y]=='.'&&gp[x][y+]=='.')
{
code[y]=code[y-]=bit;
dp[now].push(encode(m),v);
}
}
else if(!l||!up)
{
int e=l+up;
if(x<n&&gp[x+][y]=='.')
{
code[y-]=e;
dp[now].push(encode(m),v);
memcpy(code,res,sizeof(res));
}
if(y<m&&gp[x][y+]=='.')
{
code[y]=e;
dp[now].push(encode(m),v);
}
}
else if(l!=up)
{
for(int i=;i<=m;i++)
if(code[i]==up)
code[i]=l;
dp[now].push(encode(m),v);
}
else if(x==fx&&y==fy)
dp[now].push(encode(m),v);
}
LL solve()
{
dp[].clear();//初始化状态
dp[].push(,);
now=,pre=;
for(int i=;i<=n;i++)//逐格逐状态枚举转移
{
pre=now,now^=,dp[now].clear();
for(int k=;k<dp[pre].size;k++)//轮廓线行转移
dp[now].push(dp[pre].sta[k]<<inc,dp[pre].sum[k]);
for(int j=;j<=m;j++)
{
pre=now,now^=,dp[now].clear();
for(int k=;k<dp[pre].size;k++)
{
DP(i,j,k);
}
}
}
for(int i=;i<dp[now].size;i++)
if(dp[now].sta[i]==)
return dp[now].sum[i];
return ;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=;i<=n;i++)//都是从1开始
scanf("%s",&gp[i][]);
fx=fy=;
for(int i=n;i>&&!fx;i--)//寻找最终的位置
for(int j=m;j>&!fx;j--)
if(gp[i][j]=='.')
fx=i,fy=j;
if(fx==)puts("");
else cout<<solve()<<endl;
}
}