格点路线问题

kastin · 发表于 2019-4-29 16:36:25

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

本帖最后由 kastin 于 2019-4-29 16:38 编辑

原题来自数学吧：http://tieba.baidu.com/p/5956607445
题目相当于问：`n\times n` 网格，从左下角到右上角的路线有多少种。要求格点至多经过一次，且只能沿着网格线走（上下左右方向），一次只能走一个单位长度。

若将题目推广一下：
1. 格点改为 `m\times n` 的结果会是如何？
2. 格点中有部分点不能经过，该如何求解？

hujunhua · 发表于 2019-4-29 17:51:51

3. 求最长路径长度MaxLength(m,n)。

mathe · 发表于 2019-4-29 18:07:26

最长路径比较简单

mathe · 发表于 2019-4-29 18:09:47

这个计数fans应该写过代码解决过数目较小情况

mathe · 发表于 2019-4-29 20:15:14

https://oeis.org/A000532

hujunhua · 发表于 2019-4-30 08:03:00

mathe 发表于 2019-4-29 20:15
https://oeis.org/A000532

Hamilton路径要求不重复地遍历每一点，这里不要求遍历，所以数值会更大。

hujunhua · 发表于 2019-4-30 11:46:17

走格子的路线数统计问题

hujunhua · 发表于 2019-4-30 15:29:29

从左下角到右上角，非Hamiton路线，走格子的路线数
A007764

hujunhua · 发表于 2019-4-30 15:47:56

mathe 发表于 2019-4-29 18:07
最长路径比较简单

是的，如果存在Hamilton路径，就是其长度MN-1. 否则应是MN-2，漏一点不过。

账号		自动登录	找回密码
密码			欢迎注册

[转载] 格点路线问题

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

点评

点评

浏览过的版块