Ural 1519 Formula 1 插头DP进阶
Ural 1519 Formula 1 插头DP进阶
缘起
【1】中插头DP入了个小门. 而且在【1】中也提到了本题. 即本题在【1】的基础上杂糅了”连通性”. 即状压轮廓线的时候要多状压进一个信息维度——当前已经决策完毕的格子们的连通性. 所以本题可以视作在【1】的进阶. 而且墙裂推荐先学习【1】, 本文的思路就很自然了.
Ural 1519 Formula 1
问题描述
给你一个 n*m 的棋盘，有的格子是障碍，问共有多少条回路使得经过每个非障碍格子恰好一次． m, n ≤ 12．
image
如图， m = n = 4， (1, 1), (1, 2)是障碍，共有 2 条满足要求的回路．
【输入】
本题就一组数据, 第一行是n和m, 2 ≤ N, M ≤ 12, 然后是n*m的字符矩阵, *表示是障碍物. . 表示是空白.
【输出】
回路的个数. 输入保证这个数量不会超出 long long 的范围.
【样例输入】
4 4
**..
....
....
....
答案是2
4 4
....
....
....
....
答案是6
【限制】
1s 64MB本题其实在【1】中也已经预告过. 本题其实就是在【1】的基础上杂糅进了连通性——即我们需要在考虑线段覆盖的基础上还需要考虑这些插头的连通性——毕竟本题题面和【1】中的题面唯一的区别在于本题需要一条（显然非平凡）哈密顿回路，而【1】可以允许任意多条（非平凡）哈密顿回路. 所以我们不能允许下面的覆盖出现. 即下面的覆盖（即【1】中的图4）不是我们要考虑的.
回忆【1】中的做法, 【1】中我们其实是状压轮廓线上插头的存在性（存在计1, 不存在计0） ,然后决策完最后那个格子的时候, dp[n][m][0] 就是答案. 本题将延续【1】中的方法. 逐步破解本题.
ps: 这里说点废话, 关于此题, 因为是 CDQ 的入门第一题, 所以网上的题解铺天盖地. 但是如果你去看的话, 会发现N多神犇其实写的不是太清楚. 可能是神犇们觉得太显然了吧~ 但是不清不楚给小白带来的痛苦就是觉得 “哇~ 插头DP入门好难哇~”（事实上，的确没那么简单~ 但也不是遥不可及）. 本文将延续【1】（墙裂推荐大家去看看【1】，看懂【1】之后就会觉得这里的思路好自然~）
本文的宗旨（也是本人写作的一贯风格）是: 丝毫不强行解释, 而是站在小白的角度（因为本人就是）抽丝剥茧, 一点一点极为自然的，站在人思考的角度把题目解出来.
延续【1】的风格, 和【1】一样, 我们状压的依旧是轮廓线的状态. 但是我们说, 轮廓线的状态仅仅表示”插头存在性”是不够的! 也就是如果插头存在, 则记轮廓线的一段为1， 插头不存在, 则记轮廓线的一段为0. 这是不行的!
为什么? 看下图
阴影部分是障碍格子. 看到图1和图2中的黄色轮廓线, 如果仅仅使用插头存在与否的话, 那两条轮廓线的值都是 100110111, 但是能够使得轮廓线到达这一状态的图1中的黑色回路显然是不合法的. 因为它由两条哈密顿回路构成. 所以如果仅仅考虑轮廓线上的插头存在与否的问题的话, 显然是会多算的.
错误是显然的——因为没有把插头的连通性考虑进去. 那么怎么把连通性也考虑进去呢? 这里介绍网上流行的”括号表示法”. 所谓括号表示法目的就是得到轮廓线的状态（就像是【1】中使用二进制压缩轮廓线的状态一样）.
括号表示法步骤是什么呢? 首先, 观察图1中在轮廓线上方的哈密顿回路（或者说是哈密顿回路被截出来的部分, 你把轮廓线想成是海平面, 哈密顿回路是冰山, 则轮廓线上方的哈密顿回路就像是浮在海平面上方的冰山），截出的哈密顿回路的部分由A–D、B–C、E–F 三段构成. 其中A、B、E是段的起点, 而D、C、F是段的终点. 如果将起点用1表示,终点用2表示, 如果轮廓线上不存在插头的话, 就用0表示. 则图1中的轮廓线表示为 100120212, 而同理分析图2, 黑色的哈密顿回路被黄色的轮廓线截出的部分由A–F、B–C、D–E三段构成. A、B、D分别是这三段的起点，而F、C、E 分别是这三段的终点. 所以图2中的黄色轮廓线表示为100120122. 即
用【1】中的01表示法, 图1、图2中的黄色轮廓线都将表示为100110111 用括号表示法（即012表示法）, 图1，图2中的黄色轮廓线将分别表示为 100120212 和 100120122 如果将 1看做左括号的话, 2看做右括号, 0忽略掉的话, 则100120212就是 ( ( ) ) ( ), 而 100120122 就是 ( ( ) ( ) )
有点直觉的人都会发现前者给人的感觉就是不连通的（因为最外层没有一个大括号将整体包起来）, 而后者就是连通的（因为最外层存在一个大括号将整体包起来）!
所以我们就知道了——要刻画轮廓线的状态的话， 要用0、1、2三个数字来表示. 即使用三进制. 但是按照网上诸多神犇的说法——3进制没有四进制（2^2）快, 所以采用四进制更好. 于是我们知道了, 用四进制来刻（状）画（压）轮廓线. 轮廓线的状态有 4^{m+1} 至多 4^13=67108864 种状态!
仿照【1】, 我们令
令dp[i][j][k] 是当前已经决策完 第i行, 第j列的格子（1<=i<=n, 1<=j<=m）,轮廓线状态变成是k时的方案数. 0<=k<full = (4<<(m+1)). 网上很多文章都没有清楚的指明插头dp的含义. 让我这种小白猜了好久~苦啊~ QAQ
dp的初始值是 dp[1][0][0] = 1
答案是 dp[n][m][0]
但是遗憾的事情发生了
image
因为m的范围到达了12, 所以数组是开不下的（其实哪怕是我们使用三进制, 也是会MLE掉的）. 但是为了说明思路, 我们假设 数据的范围较小, 譬如 n,m<=9, 然后我会延续【1】中的思路将程序写出来, 当然，显然是无法ac的. 因为m的范围都不对. 但是我会将写好的程序和网上神犇的代码对拍, 发现没有问题，则至少说明思路没有问题. 然后再改进空间复杂度.
既然dp的含义和初始值、以及我们的目标值都已经知道了. 我们就来思考状态转移的事情.
和【1】一样, 分为逐格递推和逐行递推. 逐行递推, 也就是换行也是简单的. 和【1】中的图5一样分析知道,
for i<n
L2=L1<<2. 则有 dp[i+1][0][L2] =dp[i][m][L1]
其中 L1是决策完(i,m)格子之后的轮廓线, 而L2是决策完(i+1,0)格子之后的轮廓线.
这里之所以是<<2而不是 <<1, 是因为本题是四进制, 而不是二进制.注意, 其实上面的换行要求L1<(full>>2)（其中full=1<<(2*(m+1), full-1表示轮廓线全部是1的状态）,因为这样L2=L1<<2才不会超出full, 所以L1的四进制第m个比特位一定要求是0，即下图中蓝色竖线对应的轮廓线的比特位要求是0（即没有插头）.
其实这样就pass掉了下图这样的轮廓线状态（即路径状态）
image
因为这样的路径状态会使得轮廓线的竖线部分有插头.
再分析一下障碍格子. 和【1】的图6一样分析, 很容易知道——只有障碍格子的上左两条边都没有插头的时候, 才有如下伪代码：
L2=L1, dp[i][j][L2]=dp[i-1][j][L1]否则
dp[i][j][L2]=0, for L2 s.t. 障碍格子上左两边至少一个有插头好了, 分析完这些特殊情形, 我们来考虑正常格子的逐格递推. 如果令p和q分别是j-1段和j段的轮廓线的比特位情况（即p、q分别是是L1的左段、上段轮廓线）分别为p和q的话， 则【1】中其实是根据p=0,q=0、p=0,q=1、p=1,q=0、p=1,q=1 四种情况分情况讨论的. 只不过将p=0,q=1、p=1,q=0 这两种情况合并成了【1】中的情况3而已. 而本题, p,q的取值范围是0、1、2. 所以有 3*3=9 种情况. 也就是我们在不知晓能不能合并的情况下, 理论上是有9种情况需要分类讨论的.
为了说明方便, 令
for(int j = 0;j<=m;j++)
{
jz[j] = j<<1;
}jz的值显然是0,2,4,6,8,10… 因为本题是四进制, 所以移位的时候移动位数都是2的倍数. 并且约定图中灰色的格子默认是障碍格子.
1 p=0, q=0
其实就是【1】中的图1. 当前决策完毕格子是BGDC. 则因为每个格子一定 要有2个插头, 一个是进的, 一个是出的. 所以L2的j-1、j个比特位(即BG、GD)一定都不是0. 所以L2相比L1就是第j-1、第j个比特位变化了而已——由L1的both=0变成L2的both不为0, 不为0的话, 则一定是1、2，即形成了一对新的括号. 所以我们知道
L2=L1+(1<<jz[j-1])+2*(1<<jz[j])
dp[i][j][L2]+=dp[i][j-1][L1]注意, 这里使用的是紫书P434说的dp的刷表法而不是填表法.
2 p =0, q=1
即决策完格子ABCD之后, 轮廓线由L1=E->F->A->D->C->G 变成了 L2=E->F->A->B->C->G
p=0是L1的第j-1个4进制比特位（下面简称比特位）, q = 1是L1的第j个比特位.
而AB变成1是L2的第j-1个比特位, BC变成0是L2的第j个比特位. 因此
L2=L1-(1<<jz[j])+(1<<jz[j-1])
dp[i][j][L2]+=dp[i][j-1][L1]注意, 上面是轮廓线继续向下开拓（即从CD进入, 然后从AB穿出）. 如果轮廓线是从CD进入,然后从BC穿出的话, 就像下图一样
image
则决策完格子ABCD之后, 轮廓线由 L1=A->D->C->E 变成了L2=A->B->C->E
p=0是L1的第j-1个比特位, q=1是L1的第j个比特位.
AB=0是L2的第j-1个比特位, BC=1是L2的第j个比特位. 从而
L2=L1
dp[i][j][L2]+=dp[i][j-1][L1]3 p=0, q = 2
image
即决策完格子ABCD之后, 轮廓线由L1=F->G->A->D->C->E 变成了 L2=F->G->A->B->C->E
p=0是L1的第j-1个比特位, q = 2是L1的第j个比特位.
而AB=0是L2的第j-1个比特位, BC=2是L2的第j个比特位. 因此
L2=L1
dp[i][j][L2]+=dp[i][j-1][L1]注意, 上面是轮廓线向右开拓, 如果轮廓线向下开拓的话, 即像下面这个样子
即决策完格子ABCD之后, 轮廓线由L1=E->F->A->D->C 变成了 L2=E->F->A->B->C
p=0是L1的第j-1个比特位, q = 2是L1的第j个比特位.
而AB=2是L2的第j-1个比特位, BC=0是L2的第j个比特位. 因此
L2=L1-2*(1<<jz[j])+2*(1<<jz[j-1])
dp[i][j][L2] += dp[i][j-1][L1]4 p=1, q = 0
即决策完格子ABCD之后, 轮廓线由L1=F->A->D->C->E 变成了 L2=F->A->B->C->E
p=1是L1的第j-1个比特位, q = 0是L1的第j个比特位.
而AB=1是L2的第j-1个比特位, BC=0是L2的第j个比特位. 因此
L2=L1
dp[i][j][L2]+=dp[i][j-1][L1]当然, 还有下面的情形
即决策完格子ABCD之后, 轮廓线由L1=F->A->D->C->E 变成了 L2=F->A->B->C->E
p=1是L1的第j-1个比特位, q = 0是L1的第j个比特位.
而AB=0是L2的第j-1个比特位, BC=1是L2的第j个比特位. 因此
L2=L1-(1<<jz[j-1])+(1<<jz[j])
dp[i][j][L2]+=dp[i][j-1][L1]5 p=1, q=1
即决策完格子ABCD之后, 轮廓线由L1=E->A->D->C->F->G 变成了 L2=E->A->B->C->F->G
p=1是L1的第j-1个比特位, q = 1是L1的第j个比特位.
注意, 此时的情形和之前出现的都不一样了. L2的第j-1个、第j个比特位不仅都变成0了, 而且pp将变成1. 其中pp是和q=1匹配的那个右括号. 找到pp的具体位置x就要用到当时学习数据结构——栈的时候玩过的经典的括号匹配问题了. 因此
L2=L1-(1<<jz[j-1])-(1<<jz[j])-2*(1<<jz[x])+(1<<jz[x])
=L1-(1<<jz[j-1])-(1<<jz[j])-(1<<jz[x])
dp[i][j][L2]+=dp[i][j-1][L1]注意, 本情形不会像上面那样出现两种图, 因为p=1,q=1说明当前决策完毕的格子ABCD已经有两个插头了.
6 p=1,q=2
注意, 这个比较tricky. 而且是本题的关键.
image
显然,p=1, q=2意味着回路的闭合. 而题目要求仅仅只能有一条哈密顿回路 所以不能提早闭合. 右图发生了提早闭合（在K处）, 所以对于这种情况，是不能将轮廓线为G->F->M->Q->D->C 的dp值用于去更新dp[i][j][L2]的. 即不能用于刷表. 只有当前决策完毕的格子的i=最后的那个非障碍格子的行, j=最后那个格子的列的时候（例如上图左边）才能将此轮廓线（例如上图左边的轮廓线G->F->E->A->D->C）的dp值用于刷（更）表（新）dp[i][j][L2]. 正因为如此, 所以我们才能保证最后得到的方法数dp[n][m][0]中都是只有一条哈密顿回路的方案, 因为提前闭合的方案都没有算进来. 这也是本题和【1】的唯一本质区别! 即
if(i==nn&&j==mm)
{
L2=L1-(1<<jz[j-1])-2*(1<<jz[j]);
dp[i][j][L2]+=dp[i][j-1][L1];
}7 p=2, q = 0
即决策完格子ABCD之后, 轮廓线由L1=E->A->D->C 变成了 L2=E->A->B->C
p=2是L1的第j-1个比特位, q = 0是L1的第j个比特位.
而AB=2是L2的第j-1个比特位, BC=0是L2的第j个比特位. 因此
L2=L1
dp[i][j][L2]+=dp[i][j-1][L1]当然,我们也可以
即决策完格子ABCD之后, 轮廓线由L1=E->A->D->C->F 变成了 L2=E->A->B->C->F
p=2是L1的第j-1个比特位, q = 0是L1的第j个比特位.
而AB=0是L2的第j-1个比特位, BC=2是L2的第j个比特位. 因此
L2=L1-2(1<<jz[j-1])+2(1<<jz[j])
dp[i][j][L2]+=dp[i][j-1][L1]8 p=2, q=1
即决策完格子ABCD之后, 轮廓线由L1=F->E->A->D->C->G 变成了 L2=F->E->A->B->C->G
p=2是L1的第j-1个比特位, q = 1是L1的第j个比特位.
而AB=0是L2的第j-1个比特位, BC=0是L2的第j个比特位. 因此
L2=L1-2*(1<<jz[j-1])-(1<<jz[j])
dp[i][j][L2]+=dp[i][j-1][L1]9 p=2, q=2
和情形5: p=1,q=1类似, 就是找到和p=2配对的pp=1的位置x, 将x处的比特位改成2即可. 类似于情形5, ABCD是当前决策完毕的格子. 轮廓线由L1=E->F->G->A->D->C 变成 L2=E->F->G->A->B->C
L2=L1-2*(1<<jz[j-1])-2*(1<<jz[j])+(1<<jz[x])
dp[i][j][L2]+=dp[i][j][L1]至此, 本题涉及到的9种轮廓线变化情况都已经全部分析完毕. 知道了状态转移方程, 代码就非常好写了（事实上, 下面的kk方法几乎就是copy上面的伪代码）. 代码风格和【1】几乎一样（我非常非常看重一类题型使用几乎一样的代码风格予以解决, 而不希望一种题型这里使用一种风格的代码, 那里使用另一种风格的代码, 这是极为不利于学习、理解和记忆的）.
#include "stdafx.h"
#include <stdio.h>
#define LOCAL
typedef long long ll;
const int maxm = 10; // 这里假设m的最大是9
int n,m, lasti,lastj, full, jz[maxm+1]; // (lasti, lastj) 是最后那个非障碍格子.
ll dp[maxm][maxm][1<<maxm*2];
bool a[maxm][maxm];
int getright2(int k,int j) // 轮廓线的状态是k,找到第j个比特位(它是1)右边和它配对的那个2的位置
{
int tot = 1; // 左括号(即1)的个数
for (int i = j+1,d; i<=m; i++)
{
d = (k>>jz[i])&3;
if (d==1)
{
++tot;
}
else if (d==2)
{
--tot;
}
if (!tot)
{
return i;
}
}
return -1;
}
int getleft1(int k, int j) // 轮廓线的状态是k, 找到第j个比特位(它是2)左边和它配对的那个1的位置
{
int tot = 1; // 右括号(即2)的个数
for (int i = j-1,d; ~i; i--)
{
d = (k>>jz[i])&3;
if (d==1)
{
--tot;
}
else if (d==2)
{
++tot;
}
if (!tot)
{
return i;
}
}
return -1;
}
void kk(int i, int j)
{
for (int l1 = 0,p,q,l2,x; l1<full; l1++)
{
p = (l1>>jz[j-1])&3, q = (l1>>jz[j])&3;
ll s = dp[i][j-1][l1];
if (a[i][j])
{
if (!p)
{
if (!q)
{
l2=l1+(1<<jz[j-1])+2*(1<<jz[j]);
dp[i][j][l2]+=s;
}
else if (q==1)
{
l2=l1-(1<<jz[j])+(1<<jz[j-1]);
dp[i][j][l2]+=s;
l2=l1;
dp[i][j][l2]+=s;
}
else if (q==2)
{
l2=l1;
dp[i][j][l2]+=s;
l2=l1-2(1<<jz[j])+2(1<<jz[j-1]);
dp[i][j][l2] += s;
}
}
else if (p==1)
{
if (!q)
{
l2=l1;
dp[i][j][l2]+=s;
l2=l1-(1<<jz[j-1])+(1<<jz[j]);
dp[i][j][l2]+=s;
}
else if (q==1)
{
x = getright2(l1, j);
if (~x)
{
l2=l1-(1<<jz[j-1])-(1<<jz[j])-(1<<jz[x]);
dp[i][j][l2]+=s;
}
}
else if (q==2 && i==lasti && j==lastj) // 只有最后非障碍格子才能用于dp刷表, 确保最后答案dp[n][m][0]中的每种方案都恰好一条哈密顿回路,这是本题和【1】的本质不同之处
{
l2=l1-(1<<jz[j-1])-2*(1<<jz[j]);
dp[i][j][l2]+=s;
}
}
else if(p==2)
{
if (!q)
{
l2=l1;
dp[i][j][l2]+=s;
l2=l1-2(1<<jz[j-1])+2(1<<jz[j]);
dp[i][j][l2]+=s;
}
else if (q==1)
{
l2=l1-2*(1<<jz[j-1])-(1<<jz[j]);
dp[i][j][l2]+=s;
}
else if (q==2)
{
x = getleft1(l1, j-1);
if (~x)
{
l2=l1-2(1<<jz[j-1])-2(1<<jz[j])+(1<<jz[x]);
dp[i][j][l2]+=s;
}
}
}
}
else if(!p && !q)
{
dp[i][j][l1] = s;
}
}
}
void sz(int i)
{
for (int k = 0; k<full>>2; k++)
{
dp[i+1][0][k<<2] = dp[i][m][k];
}
}
int main()
{
#ifdef LOCAL
freopen("d:\data.in", "r", stdin);
// freopen("d:\my.out", "w", stdout);
#endif
scanf("%d%d", &n,&m);
for (int i = 0;i<=m+1; i++)
{
jz[i] = i<<1;
}
full = 1<<jz[m+1];
for (int i = 1;i<=n;i++)
{
getchar();
for (int j = 1; j<=m; j++)
{
a[i][j] = getchar()=='.';
if (a[i][j])
{
lasti = i;
lastj = j;
}
}
}
dp[1][0][0] = 1;
for (int i = 1;i<=n;i++)
{
for (int j = 1;j<=m;j++)
{
kk(i,j);
}
if (i<n)
{
sz(i);
}
}
printf("%lld", dp[n][m][0]);
return 0;
}上面的代码因为空间复杂度的原因限制了m只能<=9, 所以提交之后毫无意外的wa掉了但是对拍网上ac程序 m<=9 的情况都是正确的. 所以我们可以认为上面的思路是没有问题的. 所以下面的任务就是如何优化空间复杂度~
首先应该想想——为什么上面的代码的空间复杂度这么高?
我们先来看看上面的代码（包括【1】以及一大票这种插头DP问题）的过程——其实就是用(i,j-1)格子的4^{m+1}种状态去更新(i,j)格子的4^{m+1}种状态嘛~
话说到这里，两个优化点自然就出来了
（1）因为我们要求的是 dp[n][m][0], 而(i,j)格子的状态仅仅是(i,j-1)格子状态衍生出来的, 和(i,j-2),…,(1,1)格子的状态根本无关. 所以可以使用滚动数组的方式来优化 dp[i][j][k]为 dp[2][k], 其中k是状态。如果仅仅做到这里, 我们依旧要开 这么大的数组, 虽然比之前的 优化了很多（13*13/2=80倍）.但是数组的大小依旧达到了 2*4^13*4/1024/1024=128MB, 妥妥的MLE啊~
（2）真的有 这么多中状态吗? 其实是没有的, 例如m+1个全是1, 或者根本违反括号匹配规则的状态, 其实根本不可能在dp的时候遇到.但是我们不管三七二十一, 都用一个超大数组把他们兜住了. 这岂不是非常浪费空间? 那么如何通过这个观察来做文章将空间复杂度优化呢? 因为从 dp[1][0][0]=1出发是合法的状态. 所以我们完全可以仅仅扩展有效的状态! 也就是对于(i,j-1)格子维护它的有效状态（这里的状态指的是轮廓线的状态）队列以及状态对应的值（达到此轮廓线状态时的方法数）. 然后扩展(i,j)的时候仅仅从这个队列中拿(i,j-1)的有效状态出来扩展放进(i,j)格子的队列即可.所以
要维护 (i,j-1)格子的有效状态队列，和对应值的队列.
用(i,j-1)格子的队列去开拓(i,j)格子的队列.
说白了——就是我们仅仅保存真正会出现的情形. 而不会去管那些根本不可能出现的. 遂写下如下针对上面两点优化的代码.
而且因为我们不需要再去遍历无效的状态了, 从这一方面也会节约时间. 进一步提高效率.
//#include "stdafx.h"
#include <stdio.h>
#include <map>
using namespace std;
//#define LOCAL
typedef long long ll;
const int maxm = 13;
int n,m, lasti,lastj, jz[maxm+1], tt; // tt 用来切换ts[0]还是ts[1], ts[tt]总是当前格子(i,j), ts[tt^1]总是(i,j-1)格子
map<int, ll> ts[2]; // 这两个map分别存储(i,j-1)格子的轮廓线状态（键）以及对应的方法数（值）以及(i,j)格子的轮廓线状态（键）以及对应的方法数（值）
bool a[maxm][maxm];
typedef map<int,ll>::iterator mit;
inline int getright2(int k,int j)
{
int tot = 1;
for (int i = j+1,d; i<=m; i++)
{
d = (k>>jz[i])&3;
if (d==1)
{
++tot;
}
else if (d==2)
{
--tot;
}
if (!tot)
{
return i;
}
}
return -1;
}
inline int getleft1(int k, int j)
{
int tot = 1;
for (int i = j-1,d; ~i; i--)
{
d = (k>>jz[i])&3;
if (d==1)
{
--tot;
}
else if (d==2)
{
++tot;
}
if (!tot)
{
return i;
}
}
return -1;
}
inline void put(int l2, ll s) // 往 ts[tt] （即当前格子）中塞入(l2, s), 如果已经存在就相加
{
if (ts[tt].find(l2)!=ts[tt].end())
{
ts[tt][l2] = ts[tt][l2]+s;
}
else
{
ts[tt][l2] = s;
}
}
void kk(int i, int j)
{
int p,q,l1,l2,x;
ll s;
for (mit mt = ts[tt^1].begin(); mt!=ts[tt^1].end(); mt++)
{
l1 = mt->first;
s = mt->second;
p = (l1>>jz[j-1])&3, q = (l1>>jz[j])&3;
if (a[i][j])
{
if (!p)
{
if (!q)
{
l2=l1+(1<<jz[j-1])+2*(1<<jz[j]);
put(l2,s);
}
else if (q==1)
{
l2=l1-(1<<jz[j])+(1<<jz[j-1]);
put(l2, s);
l2=l1;
put(l2, s);
}
else if (q==2)
{
l2=l1;
put(l2, s);
l2=l1-2*(1<<jz[j])+2*(1<<jz[j-1]);
put(l2, s);
}
}
else if (p==1)
{
if (!q)
{
l2=l1;
put(l2, s);
l2=l1-(1<<jz[j-1])+(1<<jz[j]);
put(l2, s);
}
else if (q==1)
{
x = getright2(l1, j);
if (~x)
{
l2=l1-(1<<jz[j-1])-(1<<jz[j])-(1<<jz[x]);
put(l2, s);
}
}
else if (q==2 && i==lasti && j==lastj)
{
l2=l1-(1<<jz[j-1])-2*(1<<jz[j]);
put(l2, s);
}
}
else if(p==2)
{
if (!q)
{
l2=l1;
put(l2, s);
l2=l1-2*(1<<jz[j-1])+2*(1<<jz[j]);
put(l2, s);
}
else if (q==1)
{
l2=l1-2*(1<<jz[j-1])-(1<<jz[j]);
put(l2, s);
}
else if (q==2)
{
x = getleft1(l1, j-1);
if (~x)
{
l2=l1-2*(1<<jz[j-1])-2*(1<<jz[j])+(1<<jz[x]);
put(l2, s);
}
}
}
}
else if(!p && !q)
{
l2 = l1;
put(l2, s);
}
}
}
void sz(int i)
{
int l1,l2;
ll s;
for (mit x = ts[tt^1].begin(); x!=ts[tt^1].end(); x++)
{
l1 = x->first;
s = x->second;
if ((l1 >> jz[m]) & 3) // 如果 第m个比特位不为0的话, 显然不是合法状态
{
continue;
}
l2 = l1<<2;
put(l2, s);
}
}
int main()
{
#ifdef LOCAL
freopen("d:\\data.in", "r", stdin);
// freopen("d:\\my.out", "w", stdout);
#endif
scanf("%d%d", &n,&m);
for (int i = 0;i<=m+1; i++)
{
jz[i] = i<<1;
}
for (int i = 1;i<=n;i++)
{
getchar();
for (int j = 1; j<=m; j++)
{
a[i][j] = getchar()=='.';
if (a[i][j])
{
lasti = i;
lastj = j;
}
}
}
ts[tt^1][0] = 1;
for (int i = 1;i<=n;i++)
{
for (int j = 1;j<=m;j++)
{
ts[tt].clear(); // 清空当前格子对应的队列
kk(i,j); // 得到当前格子的状态队列
tt^=1; // 切换当前格子
}
if (i<n)
{
ts[tt].clear();
sz(i);
tt^=1;
}
}
printf("%lld", ts[tt^1][0]); // 因为最后tt与1做了异或(但是for循环结束了), 所以最后的答案在ts[tt^1]中而不在ts[tt]中
return 0;
}ac情况
Status Accepted Time 717ms Memory 1564kB Length 3798 Lang Visual C++ 2017 Submitted 2019-11-08 12:20:15 Shared RemoteRunId 8617887
注意, 这里为了图方便, 没有自己手写哈希表, 而是简单使用c++ stl 的map代替. 所以自然速度没有网上一些神犇手写哈希表的速度快. 但是这里把思想说清楚了. 无疑也是极好的~