题意:给一个n*m的矩阵,格子中是'*'则是障碍格子,不允许进入,其他格子都是必走的格子,所走格子形成一条哈密顿回路,问有多少种走法?

思路:

  本来是很基础的题,顿时不知道进入了哪个坑。这篇插头DP的文章够详细,推荐一看(最好不要照抄代码)。

  细节要小心,比如输出用I64d,必须用long long,判断是否无哈密顿回路,位操作等等。

  这次仍然用括号表示法,1表示(,2表示)。

 #include <bits/stdc++.h>
#define pii pair<int,int>
#define INF 0x3f3f3f3f
#define LL long long
using namespace std;
const int N=;
const int mod=;
const int NN=;
char g[N][N];
int cur, n, m, ex, ey;
struct Hash_Map
{
int head[mod]; //桶指针
int next[NN]; //记录链的信息
int status[NN]; //状态
LL value[NN]; //状态对应的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[]; 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=,t; k<hashmap[cur^].size; k++)
{
int s=hashmap[cur^].status[k];
LL v=hashmap[cur^].value[k];
int R=getbit(s,j), D=getbit(s,j+);
if(g[i][j]=='*') //障碍格子
{
if( R== && D== ) hashmap[cur].insert(s, v);
continue ;
}
if(R && D) //两个括号
{
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);
}
if( R== && D== ) //不同的连通分量
hashmap[cur].insert(t, v);
if(i==ex && j==ey && R== && D== ) //终点时'('和')'才可以合并。
hashmap[cur].insert(t, v);
}
else if(R || D) //仅1个括号
{
hashmap[cur].insert(s,v);
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);
}
} void cal()
{
if(ex==-) return ; //无空格
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 ; //终点
}
}
} LL print()
{
for(int i=; i<hashmap[cur].size; i++) //寻找轮廓线状态为0的值。
if( hashmap[cur].status[i]== )
return hashmap[cur].value[i];
return ;
}
int main()
{
//freopen("input.txt", "r", stdin);
while(~scanf("%d%d",&n,&m))
{
ex=ey=-;
cur=;
for(int i=; i<n; i++) //输入矩阵
for(int j=; j<m; j++)
{
char c=getchar();
if(c=='.'||c=='*')
{
g[i][j]=c;
if( c=='.' ) ex=i,ey=j;//终点空格
}
else j--;
} hashmap[cur].clear();
hashmap[cur].insert(, ); //初始状态
cal();
cout<<print()<<endl;
}
return ;
}

AC代码

最新文章

  1. php函数的传值如果需要引用传递注意的细节
  2. Page传回页面的值问题
  3. Android 开源项目
  4. java运算符优先级记忆口诀
  5. 剑指offer系列54---数组中出现次数超过一半的数
  6. 代码片段 - JavaScript 求时间差
  7. MacVim小试
  8. ios学习笔记之UIControl解读
  9. webapp之路--百度手机前端经验(转)
  10. 计算机程序的思维逻辑 (91) - Lambda表达式
  11. Angular4.x通过路由守卫进行路由重定向,实现根据条件跳转到相应的页面
  12. BSScrollViewEdgePop
  13. THUWC2019游记
  14. MySQL中字段字符集不同导致索引不能命中
  15. 本地jar包安装到本地仓库
  16. 【BZOJ2424】[HAOI2010]订货(费用流)
  17. SAP HANA数据库架构部署方法
  18. ethereumjs/ethereumjs-util
  19. 【codeforces666E】Forensic Examination 广义后缀自动机+树上倍增+线段树合并
  20. C语言运算符优先级和ASCII表

热门文章

  1. java:calendar类及一些比较实用的utils(二)
  2. 安装mosquitto报缺少dll文件的错误
  3. as3杂记
  4. POJ - 3253 Fence Repair 优先队列+贪心
  5. vue的踩坑路
  6. 让你头晕的VR头显,背后发生了什么?
  7. Unity3D中常用的数据结构总结与分
  8. shell chpasswd 命令 修改用户密码
  9. ZOJ 4033 CONTINUE...?(The 15th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple)
  10. 51Nod 1272 最大距离 (栈或贪心)