单行道

mathe

总体计算复杂度差别不大,只是代码要稍微复杂一些了,最后一行处理同前面各行处理有所不同,也就是代码需要特殊化一些.

gxqcn

四周新增直达路后，应该无所谓边缘问题了， 怎么还有最后一行与前面各行处理不同的问题？

无心人

GxQ提的类似一个球面上面的纵横各N条线的并行分割

mathe

是的。 为什么处理方法会不同了牵涉到这个题目的具体算法 我们假设现在有一个合理的单性道方案，我们查看如下图中的一个局部局面， 其中横向宽度为n,纵向只有一部分，而且最下面一行也只有部分方格。 对于这个一个局部局面，我们可以将所有“路口”分成两类，一类是内部路口，一类是边界路口。 其中图中用大圆点标出来的是边界路口，其余是内部路口，也就是边界路口还会同城市没有画出来的部分直接相邻， 而内部路口不会（只会通过边界路口间接沟通）。 然后我们知道，如果之看图的这一部分，那么对于任意的内部路口，都至少存在一条从这个路口到某个边界路口的有向路径； 通常，存在一条从某个边界路口到这个路口的有向路径。 而对于所有的边界路口，我们可以根据它们之间的连通关系进行分类： i)从在一条路径从一个边界路口到另外一个路口，但是另外一条方向的路径不存在（仅限于通过上图中的内部路口或边界路口） ii)存在相互到达的路径 iii)相互直接不可到达。 这个实际上是一个n个节点的简单有向图 我们可以事先计算出n个节点的简单有向图的所有数目，假设这个数目为s,然后 通过动态规划计算对于每个类似上图形状的部分图，对于边界节点形成的简单有向图的每种形状，对应的计数。 计算过程中可以从n*1的部分图开始，然后每次在下一行添加一个点（同时添加两条有向边，共4中选项） 当然实际计算中，有部分n个节点的简单有向图是永远不可能达到的，我们可以事先淘汰掉这些情况，这样就可以节省状态数目，从而提高计算速度。

mathe

有上面的算法可以知道，对于gxqcn改编以后的题目，如果采用类似上面的算法，那么每次边界节点除了考虑最下面的点以外，最上面一行同样也是边界节点（所以边界节点数目要加倍，所以问题复杂度要提高很多，我前面也没有考虑到），而在计算最后一行的时候，我们要考虑到两边的边界节点被连接起来的特殊情况（同样每一行最后一个路口添加进去的时候也有特殊情况需要处理）

无心人

呵呵，感觉GxQ的条件是把题目更复杂化了 而不是简化

mathe

也不能说复杂化，只是增加了计算难度

无心人

恩 是的 有想法了么

mathe

如我前面所说，考虑2n个点的简单图就可以了。不过这样问题复杂度要高很多。比如如果原先问题能够计算到n=14,那么估计gxqcn改编的问题基本上就只能计算到n=7了。

无心人

是否能找到不变量阿？