bzoj3125: CITY 题解
2024-09-07 12:08:57
3125: CITY
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 486 Solved: 213
[Submit][Status][Discuss]
Description
小明和小华要参加NOI,踏上了去X市的火车。
小明望着窗外的田野,大楼,工厂缓缓后退,在思考着什么。
这时,对面的小华拿出手机对着他说:“看!我们在这个位置!”
小明望着手机上显示的地图,城市被接到分割成各个方块,而自己所在的点在慢慢移动。
他突然意识到自己甚至还没游历过这个自己所在的小城市,学校和家貌以及之间来回的道路似乎成了这个小城的唯一印象。
若我把它们全部走一圈,可能要仔细计划下吧……不,那么多方案,其实我应该早能做到了吧……小明在心里对自己说。
Input
第一行有两个数N, M表示地图被分割成N*M个块,接下来有N行,每行有M个字符。
. 表示这个块可以通过
- 表示这个块只可以左右通过
| 表示这个块只可以上下通过
# 表示这个块不能通过
(从每个块只能走到其上下左右相邻的四个块)
Output
一个数,表示小明把所以可以通过的块都经过且只经过一次并回到原地的方案数。
Sample Input
Sample 1
2 2
..
..
2 2
..
..
Sample 2
Input:
4 4
....
..-.
....
....
Sample Output
Output 1
1
1
Output 2
1
HINT
数据范围: 0 < N, M < 13 不保证答案在long 范围之内
Source
联赛后第一次写题解……
这道题可以说得上是插头DP裸题了,话说最早接触插头DP是在学基础状压的时候误打误撞看到了CDQ的论文,差点入坑,然而最后我还是得入一下。
这道题比较特殊的就是‘-’ ‘|’这两个设定,但其实也很容易,我们只要在转移的时候进行特判,‘-’只能接左插头,‘|’只能接上插头。其余转移同理。但是要注意的是由于许多转移代码大体结构一样,可以直接复制粘贴,但是细节还是要去检查一下,我因为特判粘贴后位置改变却没发现调了两个小时。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 15
using namespace std;
int n,m,ma[N][N],zz,tot[];
char bb[N];
int xp[N],b[],dl[];
long long f[][],ans;
bool check(int x,int t,int sum)
{
if(sum<) return ;
if(x==m+)
return sum==;
if(b[t/xp[x]]==) return check(x+,t,sum+);
else if(b[t/xp[x]]==) return check(x+,t,sum-);
else return check(x+,t,sum);
}
int main()
{
int nn,mm;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%s",bb+);
for(int j=;j<=m;j++)
{
if(bb[j]=='.') ma[i][j]=,nn=i,mm=j;
else if(bb[j]=='-') ma[i][j]=,nn=i,mm=j;
else if(bb[j]=='|') ma[i][j]=,nn=i,mm=j;
}
}
xp[]=;
for(int i=;i<=m+;i++) xp[i]=xp[i-]*;
for(int i=;i<xp[m+];i++) b[i]=i%;
for(int i=;i<xp[m+];i++)
{
if(check(,i,))
{
zz++;
tot[zz]=i;
dl[i]=zz;
}
}
int now=,la=;
f[][]=;
for(int i=;i<=n;i++)
{
for(int j=;j<=m;j++)
{
la^=,now^=;
memset(f[now],,sizeof(f[now]));
int p,q,x=xp[j-],y=xp[j],t;
for(int k=;k<=zz;k++)
{
p=b[tot[k]/x],q=b[tot[k]/y];
t=tot[k]-p*x-q*y;
if(ma[i][j])
{
if(!p&&!q)
{
if(ma[i][j]==&&dl[t+x+(y<<)]) f[now][dl[t+x+(y<<)]]+=f[la][k];
}
else if(!q)
{
if(ma[i][j]!=)
{
if(j!=m&&dl[t+(y<<(p-))]) f[now][dl[t+(y<<(p-))]]+=f[la][k];
if(i!=n&&ma[i][j]==&&dl[t+(x<<(p-))]) f[now][dl[t+(x<<(p-))]]+=f[la][k];
}
}
else if(!p)
{
if(ma[i][j]!=)
{
if(j!=m&&ma[i][j]==&&dl[t+(y<<(q-))]) f[now][dl[t+(y<<(q-))]]+=f[la][k];
if(i!=n&&dl[t+(x<<(q-))]) f[now][dl[t+(x<<(q-))]]+=f[la][k];
}
}
else if(p==&&q==)
{
if(!t&&i==nn&&j==mm) ans+=f[la][k];
}
else if(p==&&q==)
{
if(ma[i][j]==)
{
if(dl[t]) f[now][dl[t]]+=f[la][k];
}
}
else if(p==&&q==)
{
if(ma[i][j]==)
{
int u,tmp;
for(u=j+,tmp=;u<=m&&tmp>=;tmp+=(b[t/xp[u]]==)-(b[t/xp[u]]==),u++);
u--;
if(t-xp[u]<) continue;
if(dl[t-xp[u]]) f[now][dl[t-xp[u]]]+=f[la][k];
}
}
else if(p==&&q==)
{
if(ma[i][j]==)
{
int u,tmp;
for(u=j-,tmp=;u>&&tmp>=;tmp+=(b[t/xp[u]]==)-(b[t/xp[u]]==),u--);
u++;
if(dl[t+xp[u]]) f[now][dl[t+xp[u]]]+=f[la][k];
}
}
}
else
{
if(!p&&!q&&dl[t]) f[now][dl[t]]+=f[la][k];
}
}
}
for(int j=zz;j>=;j--)
{
if(b[tot[j]]==)
{
if(dl[tot[j]/]) f[now][j]=f[now][dl[tot[j]/]];
else f[now][j]=;
}
else f[now][j]=;
}
}
printf("%lld\n",ans);
return ;
}
最新文章
- c#3.0新特性
- Spring对事务管理的支持的发展历程--转
- APP开发+发布流程
- 关于javaScript单线程的见解
- PHP 通过Socket收发16进制数据
- table下属标签与标签中间不能加其他任何标签
- Java虚拟机学习(3): 类加载机制
- BurpSuite实例教程
- CF577B Modulo Sum 好题
- TreeView1MouseMove
- 几年的Git使用技巧总结
- jQuery给CheckBox添加事件
- Apache 支持.htaccess
- 算法精解(C语言描述) 第3章 读书笔记
- SRM 583 Div II Level Three:GameOnABoard,Dijkstra最短路径算法
- HTML5离线应用与客户端存储
- Targeted Learning R Packages for Causal Inference and Machine Learning(转)
- Oracle 相关概念
- urllib2 post请求方式,带cookie,添加请求头
- tomcat 修改jdk版本号