题目链接

题解

插头dp，枚举边界线的插头，分类讨论转移点上插头和左插头的情况，来转移这个点的插头。

代码

#include 
    
     #include 
     
      #include 
      
       const int maxn=20;const int hash_mod=1007;const int maxd=maxn*maxn;const int maxk=50000;int read(){  int x=0,f=1;  char ch=getchar();  while((ch<'0')||(ch>'9'))    {      if(ch=='-')        {          f=-f;        }      ch=getchar();    }  while((ch>='0')&&(ch<='9'))    {      x=x*10+ch-'0';      ch=getchar();    }  return x*f;}struct func{  int x;  long long y;};struct hash_table{  int now[hash_mod+10],pre[maxk+2],cnt;  func val[maxk+2];  int clear()  {    cnt=0;    memset(now,0,sizeof now);    return 0;  }  long long add(int s,long long v)  {    int trans=s%hash_mod,j=now[trans];    while(j)      {        if(val[j].x==s)          {            val[j].y+=v;            return val[j].y;          }        j=pre[j];      }    val[++cnt].x=s;    val[cnt].y=v;    pre[cnt]=now[trans];    now[trans]=cnt;    return v;  }  func get(int x)  {    return val[x];  }};hash_table ht[2];int n,m,rv[maxn+4],v[maxn+2][maxd+2],now,last;char s[maxn+4];int decode(int x){  for(int i=0; i<=m; ++i)    {      rv[i]=x&3;      x>>=2;    }  return 0;}int encode(){  int res=0;  for(int i=m; ~i; --i)    {      res=(res<<2)+rv[i];    }  return res;}int findl(int pos){  int now=-1;  while(1)    {      if(rv[pos])        {          now+=(rv[pos]==1)?1:-1;        }      if(!now)        {          return pos;        }      --pos;    }}int findr(int pos){  int now=1;  while(1)    {      if(rv[pos])        {          now+=(rv[pos]==1)?1:-1;        }      if(!now)        {          return pos;        }      ++pos;    }}int expand(int x,int y,func from){  decode(from.x);  int west=rv[m],north=rv[y];  if((!y)&&west)    {      return 0;    }  if(v[x][y])    {      if(west||north)        {          return 0;        }      ht[now].add(encode(),from.y);    }  else if(west&&north)    {      rv[m]=rv[y]=0;      if(west