1814: Ural 1519 Formula 1

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 924  Solved: 351
[Submit][Status][Discuss]

Description

 一个 m * n 的棋盘,有的格子存在障碍,求经过所有非障碍格子的哈密顿回路个数

Input

The first line contains the integer numbers N and M (2 ≤ N, M ≤ 12). Each of the next N lines contains M characters, which are the corresponding cells of the rectangle. Character "." (full stop) means a cell, where a segment of the race circuit should be built, and character "*" (asterisk) - a cell, where a gopher hole is located.

Output

You should output the desired number of ways. It is guaranteed, that it does not exceed 2^63-1.

Sample Input

4 4
**..
....
....
....

Sample Output

2
分析:今天把插头dp学了一下,没想到dp还能写这么长......细节什么的也很多,在这里当一个模板吧.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
typedef long long ll; const int maxn = ;
const int pow[] = {,,,,,,,,,,,,};
int n,m,now,pre,tx,ty;
char map[][]; struct node
{
int head[maxn],nextt[maxn],tot;
ll sum[maxn],sta[maxn];
void clear()
{
memset(head,-,sizeof(head));
tot = ;
}
void push(ll x,ll v)
{
ll hashh = x % maxn;
for (int i = head[hashh]; i >= ; i = nextt[i])
{
if (sta[i] == x)
{
sum[i] += v;
return;
}
}
sta[tot] = x;
sum[tot] = v;
nextt[tot] = head[hashh];
head[hashh] = tot++;
}
} f[]; int turnleft(ll x,int k)
{
return x << pow[k];
} int get(ll x,int k)
{
return (x >> pow[k]) & ;
} ll del(ll x,int i,int j)
{
return x & (~( << pow[i])) & (~( << pow[j]));
} int findr(ll x,int pos)
{
int cnt = ;
for (int i = pos + ; i <= m; i++)
{
int k = get(x,i);
if (k == )
cnt++;
else if (k == )
cnt--;
if (!cnt)
return i;
}
} int findl(ll x,int pos)
{
int cnt = ;
for (int i = pos - ; i >= ; i--)
{
int k = get(x,i);
if (k == )
cnt++;
else if (k == )
cnt--;
if (!cnt)
return i;
}
} void solve2(int x,int y,int k)
{
int p = get(f[pre].sta[k],y - ); //右插头
int q = get(f[pre].sta[k],y); //下插头
ll staa = del(f[pre].sta[k],y - ,y); //将这两个插头删掉以后的状态
ll v = f[pre].sum[k];
if (!p && !q) //新建一个连通分量
{
if (map[x][y] == '*')
{
f[now].push(staa,v);
return;
}
if (x < n && y < n && map[x + ][y] == '.' && map[x][y + ] == '.')
f[now].push(staa | turnleft(,y - ) | turnleft(,y),v);
}
else if (!p || !q) //保持原来的连通分量
{
int temp = p + q;
if (x < n && map[x + ][y] == '.')
f[now].push(staa | turnleft(temp,y - ),v);
if (y < m && map[x][y + ] == '.')
f[now].push(staa | turnleft(temp,y),v);
}
else if (p == && q == ) //连接两个联通分量
f[now].push(staa ^ turnleft(,findr(staa,y)),v); //这里的异或实际上就是把1变成2,2变成1
else if (p == && q == )
f[now].push(staa ^ turnleft(,findl(staa,y - )),v);
else if (p == && q == )
f[now].push(staa,v);
else if (x == tx && y == ty)
f[now].push(staa,v);
} ll solve()
{
f[].clear();
f[].push(,);
now = ,pre = ; //滚动数组
for (int i = ; i <= n; i++)
{
pre = now;
now ^= ;
f[now].clear();
for (int k = ; k < f[pre].tot; k++)
f[now].push(turnleft(f[pre].sta[k],),f[pre].sum[k]); //左移一位,因为轮廓线下来的时候会少一个插头
for (int j = ; j <= m; j++)
{
pre = now;
now ^= ;
f[now].clear();
for (int k = ; k < f[pre].tot; k++)
solve2(i,j,k); //处理第k个状态
}
}
for (int i = ; i < f[now].tot; i++)
if (f[now].sta[i] == ) //没有插头了.
return f[now].sum[i];
return ;
} int main()
{
scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++)
scanf("%s",map[i] + );
for (int i = ; i <= n; i++)
for (int j = ; j <= m; j++)
if (map[i][j] == '.')
tx = i,ty = j; //找右下角的非障碍点
if (!tx)
puts("");
else
printf("%lld\n",solve()); return ;
}

最新文章

  1. TCP/IP三次握手和HTTP过程
  2. ZooKeeper的Znode剖析
  3. Java 获取两个日期之间的日期
  4. python scrapy版 极客学院爬虫V2
  5. msg url
  6. Jenkins运行完Test后,把ngreport生成的测试报告 拷贝到相应的文件夹
  7. 分享:mysql 随机查询数据
  8. 文件上传(FileUpload控件)
  9. 软件测试 -- 测试人员和QA的区别
  10. ubuntu基本操作(2)
  11. ibatis错误
  12. poj1935
  13. ThinkPHP文件上传类
  14. ALV双击单元格事件处理
  15. Node.js学习 - Global Object
  16. Could not execute JDBC batch update; SQL [delete from role where roleId=?]; constraint [null]; neste
  17. Zabbix 监控触发器设置
  18. 别以为真懂Openstack: 虚拟机创建的50个步骤和100个知识点(1)
  19. CardView卡片式布局
  20. 泛型--增强for循环--数组和集合转换

热门文章

  1. (数据科学学习手札02)Python与R在循环语句与条件语句上的异同
  2. web框架与爬虫
  3. linux基础重要命令小节
  4. 使用USB Key(加密狗)实现身份认证
  5. 步骤1:JMeter 录制脚本接口测试
  6. @property, @classmethod基本用法
  7. centos7使用Gogs搭建Git服务器
  8. CodeForces-455A Boredom
  9. win10激活方法-专业版
  10. 解决:Unable to execute dex: GC overhead limit exceeded