题意：给一个n*m的矩阵，其中#是障碍格子，其他则是必走的格子，问从左下角的格子走到右下角的格子有多少种方式。
思路：
注意有可能答案是0，就是障碍格子阻挡住了去路。
插头DP有两种比较常见的表示连通信息的方式：
（1）最小表示法
（2）括号表示法
本文用括号表示法实现。左括号为1，右括号为2，用两个位来表示。轮廓线上最多需要表示9个插头信息，那么就是18个位即可。插头的状态转移有如下几种：
（1）右插头和下插头都是同个方向的括号，则合并他们，再将对应的两外两个半括号给改成一对。比如 ((())) 合并完变成##()()，橙色的就是需要改的地方。
（2）右插头是')'，下插头是'('，则合并他们，且无需任何修改。
（3）右插头是'('，下插头是')'，则不能合并，因为一旦合并，肯定是组成1个圆了，就会有多个连通分量的产生。自己画画就知道了。
（4）右插头是'('，下插头是')'，只有在最后一个非障碍格子（按行从左到右遍历的）的时候才可以合并，
（5）右/下插头只有1个插头存在，那么可以延续它，可以分别往下和右两个方向。
（6）没有插头，那么只能另开一对新括号了，分别对应右和下插头的位置。
（7）障碍格子，只有该位置的两个插头都是空的时候才可以转移，且轮廓线无需修改。
因为状态本来就不多，用哈希表来存状态会比较快且比较省时间，哈希表实现是摘别人的。每次只需要用上一个格子中的状态来转移到当前格子的状态。本题是不能有连通分量产生的，所以只需要在初始的状态设置起点和终点是一对括号，那就相当于在找哈密顿回路了，和Formula 1就一样了。
//#include <bits/stdc++.h>
#include <iostream>
#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
char g[N][N];
int cur, n, m, ex, ey;
struct Hash_Map
{
static const int mod=;
static const int N=;
int head[mod]; //桶指针
int next[N]; //链
int status[N]; //状态
LL value[N]; //状态对应的DP值。
int size;
void clear()
{
memset(head, -, sizeof(head));
size = ;
} void insert(int st, LL val) //插入状态st的值为val
{
int h = st%mod;
for(int i=head[h]; i!=-; i=next[i])
{
if(status[i] == st) //这个状态已经存在，累加进去。
{
value[i] += val;
return ;
}
}
status[size]= st; //新的
value[size] = val;
next[size] = head[h] ; //新插入的元素在队头
head[h] = size++;
}
}hashmap[]; int getbit(int s,int pos) //取出状态s的第pos个插头
{
int bit=;
if(s&(<<*pos)) bit+=;
if(s&(<<*pos+)) bit+=;
return bit;
}
int setbit(int s,int pos,int bit) //将状态s的第pos个插头设置为bit
{
if(s&(<<*pos )) s^=<<*pos;
if(s&(<<*pos+)) s^=<<*pos+;
return s|(bit<<*pos);
} int Fr(int s,int pos,int bit) //寻找状态s的第pos个插头对应的右括号。
{
int cnt=;
for(pos+=; pos<m; pos++)
{
if(getbit(s,pos)==-bit) cnt++;
if(getbit(s,pos)==bit) cnt--;
if(cnt==-) return setbit(s, pos, -bit);
} }
int Fl(int s,int pos,int bit) //寻找状态s的第pos个插头对应的左括号。
{
int cnt=;
for(pos--; pos>=; pos--)
{
if(getbit(s,pos)==-bit) cnt++;
if(getbit(s,pos)==bit) cnt--;
if( cnt==-) return setbit(s, pos, -bit);
} } void DP(int i,int j) //状态转移
{
for(int k=; k<hashmap[cur^].size; k++)
{
int s=hashmap[cur^].status[k];
int v=hashmap[cur^].value[k];
int R=getbit(s,j), D=getbit(s,j+);
if(g[i][j]=='.')
{
if(R && D) //两个括号
{
int t=setbit(s,j,)&setbit(s,j+,);
if(R==D) //同个方向的括号
{
if(R==) t=Fr(t,j,); //要改
else t=Fl(t,j,);
hashmap[cur].insert(t,v);
}
else if( R== && D== ) //不同方向括号
hashmap[cur].insert(t,v);
else if(i==ex&&j==ey)
hashmap[cur].insert(t,v);
}
else if(R || D) //仅1个括号
{
hashmap[cur].insert(s,v);
int t;
if(R) t=setbit(setbit(s,j,),j+,R);
else t=setbit(setbit(s,j+,),j,D);
hashmap[cur].insert(t,v);
}
else //无括号
hashmap[cur].insert( setbit(s,j,)|setbit(s,j+,), v);
}
else if(R==&&D==) //障碍格子
hashmap[cur].insert(s, v);
}
}
void cal()
{
for(int i=; i<n; i++)
{
cur^=;
hashmap[cur].clear();
for(int j=; j<hashmap[cur^].size; j++) //新行，需要左移一下状态。
if( getbit( hashmap[cur^].status[j], m)== )
hashmap[cur].insert( hashmap[cur^].status[j]<<, hashmap[cur^].value[j] );
for(int j=; j<m; j++)
{
cur^=;
hashmap[cur].clear();
DP(i,j);
if(i==ex && j==ey) return ; //终点
}
}
} bool print()
{
for(int i=; i<hashmap[cur].size; i++) //寻找轮廓线状态为0的值。
{
int s=hashmap[cur].status[i];
if(s==)
{
printf("%lld\n", hashmap[cur].value[i]);
return true;
}
}
return false;
}
int main()
{
freopen("input.txt", "r", stdin);
while(scanf("%d%d",&n,&m), n+m)
{
ex=ey=cur=;
for(int i=n-; i>=; i--) scanf("%s",g[i]); //反向存
for(int i=; i<n; i++) //寻找终点格子：ex和ey
for(int j=; j<m; j++)
if( g[i][j]=='.' )
ex=i,ey=j; hashmap[cur].clear();
hashmap[cur].insert(setbit(,,)|setbit(,m-,), ); //初始状态
cal();
if(!print()) puts(""); //无路可达
}
return ;
}
AC代码
附上哈希表实现：
struct Hash_Map
{
static const int mod=;
static const int N=;
int head[mod]; //桶指针
int next[N]; //记录链的信息
int status[N]; //状态
LL value[N]; //状态对应的DP值。
int size;
void clear() //清除哈希表中的状态
{
memset(head, -, sizeof(head));
size = ;
} void insert(int st, LL val) //插入状态st的值为val
{
int h = st%mod;
for(int i=head[h]; i!=-; i=next[i])
{
if(status[i] == st) //这个状态已经存在，累加进去。
{
value[i] += val;
return ;
}
}
status[size]= st; //找不到状态st，则插入st。
value[size] = val;
next[size] = head[h] ; //新插入的元素在队头
head[h] = size++;
}
}hashmap[];
Hash_Map