Description
小明和小华要参加NOI，踏上了去X市的火车。
小明望着窗外的田野，大楼，工厂缓缓后退，在思考着什么。
这时，对面的小华拿出手机对着他说：“看！我们在这个位置！”
小明望着手机上显示的地图，城市被接到分割成各个方块，而自己所在的点在慢慢移动。
他突然意识到自己甚至还没游历过这个自己所在的小城市，学校和家貌以及之间来回的道路似乎成了这个小城的唯一印象。
若我把它们全部走一圈，可能要仔细计划下吧……不，那么多方案，其实我应该早能做到了吧……小明在心里对自己说。
Input
第一行有两个数N, M表示地图被分割成N*M个块，接下来有N行，每行有M个字符。
. 表示这个块可以通过
- 表示这个块只可以左右通过
| 表示这个块只可以上下通过
# 表示这个块不能通过
（从每个块只能走到其上下左右相邻的四个块）
Output
一个数，表示小明把所以可以通过的块都经过且只经过一次并回到原地的方案数。
Sample Input
Sample 1
2 2
..
..
Sample 2
Input:
4 4
….
..-.
….
….
Sample Output
Output 1
1
Output 2
1
HINT
数据范围: 0 < N, M < 13 不保证答案在long 范围之内
题解：
插头DP，跟入门题Formula 1几乎一模一样，改一下转移时的判断就行了。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define LL long long
const int mod=100037;
int n,m,map[15][15],xx=-1,yy,now=0,list[2][mod],num[2];
// 状态列表 状态总数
LL state[2][mod],ans=0;
int HASH[mod];//每种状态的数目
LL get(int s,int p)//获取状态s从右向左数的第p位
{
return (s>>((p-1)*2))&3;}
void change(int &s,int p,int v)//把状态s的第p位改成v
{s^=get(s,p)<<((p-1)*2);s^=(v)<<((p-1)*2);
}
void add(int now,int st,LL sum)
{int ss=st%mod;while(list[now][HASH[ss]]!=st&&HASH[ss]!=-1){ss++;ss%=mod;if(ss==0)ss=1;}if(HASH[ss]==-1){HASH[ss]=++num[now];list[now][num[now]]=st;state[now][num[now]]=sum;}else state[now][HASH[ss]]+=sum;
}
void work()
{state[0][1]=1;num[0]=1;list[0][1]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){now^=1;num[now]=0;memset(HASH,-1,sizeof(HASH));for(int k=1;k<=num[now^1];k++){int st=list[now^1][k];//获取上次的状态 LL sum=state[now^1][k];//获取此状态的数目int p=get(st,j);//获取上次的两个插头 int q=get(st,j+1);if(!map[i][j])//障碍点{if(!p&&!q)add(now,st,sum);continue;}if(!p&&!q)//没有连到当前的格子 {if(map[i][j]==1&&map[i][j+1]&&map[i+1][j]&&map[i][j+1]!=3&&map[i+1][j]!=2){change(st,j,1);change(st,j+1,2);add(now,st,sum);}}else if(!p&&q){if(map[i][j]!=3&&map[i][j+1]&&map[i][j+1]!=3)add(now,st,sum);if(map[i][j]!=2&&map[i+1][j]&&map[i+1][j]!=2){change(st,j,q);change(st,j+1,0);add(now,st,sum);}}else if(p>0&&!q){if(map[i][j]!=2&&map[i+1][j]&&map[i+1][j]!=2)add(now,st,sum);if(map[i][j]!=3&&map[i][j+1]&&map[i][j+1]!=3){change(st,j,0);change(st,j+1,p);add(now,st,sum);}}else if(p==1&&q==2){if(i==xx&&j==yy)ans+=sum;}else if(p==2&&q==1){change(st,j,0);change(st,j+1,0);add(now,st,sum);}else if(p==1&&q==1){int top=1;for(int pos=j+2;pos<=m+1;pos++){int temp=get(st,pos);if(temp==1)top++;if(temp==2)top--;if(top==0){change(st,j,0);change(st,j+1,0);change(st,pos,1);add(now,st,sum);break;}}}else if(p==2&&q==2){int top=1;for(int pos=j-1;pos;pos--){int temp=get(st,pos);if(temp==2)top++;if(temp==1)top--;if(top==0){change(st,j,0);change(st,j+1,0);change(st,pos,2);add(now,st,sum);break;}}}}}for(int j=1;j<=num[now];j++)list[now][j]<<=2;}
}
int main()
{memset(map,0,sizeof(map));scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){char str[15];scanf("%s",str);for(int j=1;j<=m;j++){if(str[j-1]=='.')map[i][j]=1,xx=i,yy=j;else if(str[j-1]=='-')map[i][j]=2;else if(str[j-1]=='|')map[i][j]=3;}}if(xx==-1){
puts("0");return 0;}work();printf("%lld",ans);
}