USACO/betsy

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

这是USACO Chapter 6 .5中的OI题目Betsy's Tour的介绍及题解，参见 翻译，C语言代码，C++语言代码，Pascal语言代码。

问题分析

搜索

这道题要使用DFS加上优化才可以过。 朴素的搜索只能解决到N=5，6会超时。于是要加上一些优化。 //路人表示朴素能把6过掉 路人①表示能过掉6的一定不是最朴素的 //路人②表示最朴素的回溯过六个点无压力(第6个0.4s)//路人③表示提前到达终点的情况return了，最朴素的算法6稳稳能过

优化1

不走死胡同！所谓死胡同，就是走进去以后就再也无法走出来的点。

一种简单的想法是:"任意时刻，必须保证和当前所在位置不相邻的未经点至少有两个相邻的未经点"。基于这种想法，可以采取这样的优化：

1. 当前点周围的点D,如果只有一个与D相邻的未经点,则点D为必经点。
2. 显然，如果当前点周围有两个或两个以上的符合上述条件的必经点，则无论走哪个必经点都会造成一个死胡同，需要剪枝。
3. 如果当前点周围只有一个必经点，则一定要走到这个点。
4. 如果该点周围没有必经点，则需要枚举周围每一个点。

该优化的力度很大，可以在0.2秒内解决N=6，但N=7仍然需要2秒左右的时间。

路人③补充一下：终点不能算作必经点

优化2

不要形成孤立的区域！如果行走过程中把路一分为二，那么肯定有一部分再也走不到了，需要剪枝。

形成孤立的区域的情况很多，如果使用Floodfill找连通块，代价会很大，反而会更慢。我只考虑了一种最容易出现特殊情况，即：

1. 当前点左右都是已经点(包括边缘)，而上下都是未经点
2. 当前点上下都是已经点(包括边缘)，而左右都是未经点

这样就会形成孤立的区域，只要将出现这种情况的状态都剪掉即可。

加上优化2，N=7也能在0.3s解决了。

路人甲:用Floodfill可以在15s内跑出N=7, N=6仅需0.1s, 速度不会更慢, 当且仅当填充点周围可填充点为2时Floodfill即可.

路人乙：第一种情况下特判g[0][n-1],第二种情况下特判g[n-1][n-1]即可

路人丙： 对于边缘情况还有一个小优化，因为起点固定，所以，

如果在左右边缘，只能向下搜索

如果在上边缘只能向右搜索，

如果在下边缘只能向左搜索，

这个可以优化推广到非边缘状况，在直线撞墙（或者是撞到已经走过的路线）的时候，

如果先前连续3次转向相同（向左或者向右），再往同一方向转向必然是死路（围成矩形）。

但是这样判断代价较大，效果不明显。（tangyan022）

常数优化

Pascal的时限还是蛮紧的，应尽量减少函数/过程/循环，实在不行使用inline也可以大幅加速

基于连通性状态压缩的动态规划

参见WC2008的雅礼中学陈丹琦论文《基于连通性状态压缩的动态规划》

小技巧：

终点和起点间连一条“[”形的边，将哈密顿路转换成哈密顿回路，就不需要独立插头和一大堆繁琐的判断了

再将棋盘顺时针旋转90度，更加简化了问题

详见C++源代码

另外，哪位大牛会写独立插头的，请贴个代码还有写一点注释，谢谢

独立插头增加两种情况。 假设当前轮廓线为s,当前处理位置为i, x = s[i] y = s[i+1] 0：空 1：连通性左括号 2：连通性右括号 3：独立插头

case1:x和y中一个是3，另一个是0。实质上和x和y中一个是1，另一个是0一样的。 case2:x和y中一个是3，另一个是1、2。这个时候就把1/2连着的另一个插头改成3，当前位置两个都设为0（空）即可。

只考虑从起点开始的独立插头。注意不会出现两个独立插头，所以没有两个都是3的情况。 最后答案为结束后的轮廓线中，最后两个位置中有一个为3的状态数。

另外一种方法

（大概是黑书上的方法）

逐列递推

last[i]=0表示第i行的格子与起点连通，否则表示在这一列中与这一格连通的格子的最小行号（如果没有，则last[i]=i）

可以知道last数组有(n+1)!种情况（2*3*4*...*(n+1)=(n+1)!）

c[i]=1表示第i行的格子与它右边的格子连通，否则不连通（这一点黑书上没讲，但判断路线可行性好像要用）

f[i][j][k]表示前i行，last数组压缩后为j，c数组压缩后为k的方案数

则对于每个f[i][j][k]，枚举下一行的情况，更新f值

则初始状态f[0][0][0]=1，目标为f[n][0][0]

但是直接写会MLE，注意到很多f值都是0，所以我们用队列扩展（类似记忆化BFS）

用一个循环队列存不是0的状态

/* 队列中每个元素值存上述i,j,k,和方法数x

再开一个vis数组判重即可（注意n<=7，判重用short，出现重复的把原来这个值的位置的x加上当前值即可）

——————路人m补充

• /

试验发现队列大小1000就够了

代码见C语言程序中y1y2t341的程序

参考代码

C

C++

Pascal