论坛 › 难题征解 › 格点路线问题

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，漏一点不过。

查看完整版本: 格点路线问题