魔方吧·中文魔方俱乐部

标题: 想破我脑袋的难题，谁帮帮我 [打印本页]

作者: Osullivan 时间: 2009-6-10 20:34:41 标题: 想破我脑袋的难题，谁帮帮我

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

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

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

附件: 未命名.jpg (2009-6-10 20:36:21, 13.53 KB) / 下载次数 46
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ4NDV8ZjQ5N2FiZDd8MTcxNjAxNzIzNXwwfDA%3D

作者: 蚂蚁儿 时间: 2009-6-10 20:39:50

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

作者: superacid 时间: 2009-6-10 21:38:33

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

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

作者: 咖啡味的茶 时间: 2009-6-10 22:33:55

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

作者: lulijie 时间: 2009-6-10 23:52:55

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

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

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

附件: 111.JPG (2009-6-10 23:52:55, 16.39 KB) / 下载次数 28
http://bbs.mf8-china.com/forum.php?mod=attachment&aid=NTQ4ODB8ODVjZTdmZTN8MTcxNjAxNzIzNXwwfDA%3D

作者: lulijie 时间: 2009-6-11 00:49:45

用 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 时间: 2009-6-11 01:27:19

路过
提示下：建立递归关系可以从整个网格的尺寸(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 时间: 2009-6-11 09:09:34

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

作者: xdgtzsyyj 时间: 2009-6-11 13:32:51

有点深奥，可以简单点吗

作者: isaacking 时间: 2009-6-11 13:39:30

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

作者: yq_118 时间: 2009-6-11 16:56:44

转的好晕，楼主慢慢转把

作者: Hugh晓云 时间: 2009-6-11 17:05:09

挺有意思的，看懂了不过没耐心解……

作者: 龙魔 时间: 2009-6-11 20:45:22

俺数学学的不好不会

作者: bhw19930503 时间: 2009-6-12 16:15:41

这个我还真不会啊..

作者: 露天粮仓 时间: 2009-6-12 16:51:06

高手们，

吼吼

作者: 夜雨听风 时间: 2009-6-12 22:37:59

能不能白话点~！！！！！！！

作者: JAVE 时间: 2009-6-13 13:04:05

我弄不明白呢。

作者: Simpler 时间: 2009-6-14 10:47:54

我记得这个好像别人给我出过简化版是不可解的好像是什么奇偶的关系

欢迎光临魔方吧·中文魔方俱乐部 (http://bbs.mf8-china.com/)