想破我脑袋的难题，谁帮帮我

Osullivan

给定一个不超过2000*2000的网格，你在最左下角的位置（即(0,0)点），你的目的地在(x,y)。要求你的路线不得经过同一个交叉点两次，且不允许左转（题目背景让这个条件顺理成章：街道靠右行，左转不方便），问合法的路线共有多少种。题目难点就是你不一定要走最近的路，完全允许你绕上一大圈；这破坏了有序性，很难构造出递推公式或动态规划模型。稍微画一下图，我们发现了一些显然但很有启发性的规律：每一次右转后，你左手边方向的所有区域都不能再走了，这很可能产生出规模更小的子问题来。另外，所有合法路线必然是有如螺旋线一样的一圈一圈绕着终点走，这种隐藏的有序性也为动态规划提供了可能。


高手们，你们的show time到了~~~~~~~~~~~~~
吼吼~~~~~~~~~

[ 本帖最后由 Osullivan 于 2009-6-10 20:37 编辑 ]

蚂蚁儿

看了几遍题，没懂
对不住了，占了沙发

superacid

我肯定用DP的，不过也不方便

[ 本帖最后由 superacid 于 2009-6-10 21:40 编辑 ]

咖啡味的茶

我觉得未必能用现有的运算符号去表达。。。

lulijie

我先谈谈我的思路：
第一次拐弯处的坐标，横坐标不变，只要确定纵坐标，记作y1，
第二次拐弯处的坐标，纵坐标不变，只要确定横坐标，记作x1，
第三次拐弯处的坐标，横坐标不变，只要确定纵坐标，记作y2，
第四次拐弯处的坐标，纵坐标不变，只要确定横坐标，记作x2，
依此类推，这些数构成一串数据，每一串数据代表一种路线。
可以以下面的填充方法填充这串数据。

第一、三行的每个格子的数据，必须介于 左边相邻格子的数据和Y之间，可以等于Y，但不能等于 左边相邻格子的数据。
第二、四行的每个格子的数据，必须介于 左边相邻格子的数据和X之间，可以等于X，但不能等于 左边相邻格子的数据。
一旦出现第一或三行填充的某格数据等于Y，或第二或四行填充的某格数据等于X，填充过程就结束，这串数据就代表一种路线。
比如填充y1时，它必须介于2001和y之间，可选择的数据必须小于2001，大于等于y，同行的数据越填越小，一旦选择了y，填充过程就结束，路线已经确定。
这四行填充数据过程互不干扰，相互不影响，直到它们等于y或x为止。
总路线数就等于数据串的总可能数。

[ 本帖最后由 lulijie 于 2009-6-10 23:54 编辑 ]

lulijie

用 C(m,n) 表示从m个中取n个数的组合数。    若n>m 那么组合数等于0。
假设填充过程在第一行结束，第一行共填充了k+1个数据,那么第k+1个数据就是y，前面有k个数据，介入2001和y之间,总共填充可能为C(2000-y,k)种
                                             第二行总共填充了k个数据，介入2001和x之间, 总共填充可能为C(2000-x,k)种
                                             第三行总共填充了k个数据，介入-1和y之间,总共填充可能为C(y,k)种
                                             第四行总共填充了k个数据，介入0和x之间,总共填充可能为C(x-1,k)种
                 填充过程在第一行结束，第一行共填充了k+1个数据的可能性为C(2000-y,k)*C(2000-x,k)*C(y,k)*C(x-1,k)
                 填充过程在第一行结束的所有可能性为    ∑ C(2000-y,k)*C(2000-x,k)*C(y,k)*C(x-1,k)      
假设填充过程在第二行结束，第二行共填充了k+1个数据,那么第k+1个数据就是x，前面有k个数据，介入2001和x之间,总共填充可能为C(2000-x,k)种
                                             第一行总共填充了k+1个数据，介入2001和y之间, 总共填充可能为C(2000-y,k+1)种
                                             第三行总共填充了k个数据，介入-1和y之间,总共填充可能为C(y,k)种
                                             第四行总共填充了k个数据，介入0和x之间,总共填充可能为C(x-1,k)种
                 填充过程在第二行结束，第二行共填充了k+1个数据的可能性为C(2000-y,k+1)*C(2000-x,k)*C(y,k)*C(x-1,k)
                 填充过程在第二行结束的所有可能性为    ∑ C(2000-y,k+1)*C(2000-x,k)*C(y,k)*C(x-1,k)      
假设填充过程在第三行结束，第三行共填充了k+1个数据,那么第k+1个数据就是y，前面有k个数据，介入-1和y之间,总共填充可能为C(y,k)种
                                             第一行总共填充了k+1个数据，介入2001和y之间,总共填充可能为C(2000-y,k+1)种
                                             第二行总共填充了k+1个数据，介入2001和x之间, 总共填充可能为C(2000-x,k+1)种
                                             第四行总共填充了k个数据，介入0和x之间,总共填充可能为C(x-1,k)种
                 填充过程在第三行结束，第三行共填充了k+1个数据的可能性为C(2000-y,k+1)*C(2000-x,k+1)*C(y,k)*C(x-1,k)
                 填充过程在第三行结束的所有可能性为    ∑ C(2000-y,k+1)*C(2000-x,k+1)*C(y,k)*C(x-1,k)      
假设填充过程在第四行结束，第四行共填充了k+1个数据,那么第k+1个数据就是x，前面有k个数据，介入0和x之间,总共填充可能为C(x-1,k)种
                                             第一行总共填充了k+1个数据，介入2001和y之间, 总共填充可能为C(2000-y,k+1)种
                                             第二行总共填充了k+1个数据，介入2001和x之间,总共填充可能为C(2000-x,k+1)种
                                             第三行总共填充了k+1个数据，介入-1和y之间,总共填充可能为C(y,k+1)种
                 填充过程在第四行结束，第四行共填充了k+1个数据的可能性为C(2000-y,k+1)*C(2000-x,k+1)*C(y,k+1)*C(x-1,k)
                 填充过程在第四行结束的所有可能性为    ∑ C(2000-y,k+1)*C(2000-x,k+1)*C(y,k+1)*C(x-1,k)      

所以总的可能性为    ∑ C(2000-y,k)*C(2000-x,k)*C(y,k)*C(x-1,k)   +∑ C(2000-y,k+1)*C(2000-x,k)*C(y,k)*C(x-1,k)   +∑ C(2000-y,k+1)*C(2000-x,k+1)*C(y,k)*C(x-1,k)    +∑ C(2000-y,k+1)*C(2000-x,k+1)*C(y,k+1)*C(x-1,k)

ouditianna

路过
提示下：建立递归关系可以从整个网格的尺寸(mxn)开始，记总路径数为T(m,n; x, y)。其中(x,y)是目标点的坐标，固定，以下省略。

步骤是：考虑小一点的网格，如m变成m-1时，总路径数如何变化？这样就得到了一个方程，大概是关于T(m,n)、T(m-1,n)以及T(m-1,n-1)的。

最后会得到一个2阶的递推关系。期待你自己得出T(m,n)的公式哦！

w21531

太高深了，俺数学学的不好，就当路过了

xdgtzsyyj

有点深奥，可以简单点吗

isaacking

太高深了...不过我认为从终点左转出来到起点,这样去解可能比较简单,个人意见,仅供参考