论坛 › 算法交流 › 从3×3网格的左下角到右上角有几种走法？

王守恩 发表于 2021-4-18 09:41:16

从3×3网格的左下角到右上角有几种走法？

从3×3网格的左下角点到右上角点有几种走法？每个格点最多经过1次。

aimisiyou 发表于 2021-4-19 09:04:43

BFS。

hujunhua 发表于 2021-4-19 09:44:28

高中时期的一个经典问题，老师教我们用各种方法来转化这个问题。
印象最深的方法还是递推法。
到达点(m, n)【左下角为(0,0)】的所有路线可分为两类：或者经过它的左邻(m, n-1)，或者经过它的下邻(m-1, n)。所以\若把这个网格向右旋转45°，这不正是杨辉三角吗？所以\具体到本题，就是`C_{2+2}^2=6`.

mathe 发表于 2021-4-19 15:56:42

应该是12种

mathe 发表于 2021-4-20 12:43:18

找到答案了
https://bbs.emath.ac.cn/thread-517-1-1.html
http://oeis.org/A007764

aimisiyou 发表于 2021-4-20 13:58:40

3×3网格

3X3网格是下图右所示吧。

那么BFS的最长搜索距离是16-1=15，期间判断路径是否有回路，是否出界，是否到达右上角。
对于n×n网格，最长步数为(n+1)×(n+1)，中间节点到达终点就终止。

王守恩 发表于 2021-4-20 15:54:55

aimisiyou 发表于 2021-4-20 13:58
3×3网格是下图右所示吧。
那么BFS的最长搜索距离是16-1=15，期间判断路径是否有回路，是否出界，是否到达 ...

我的目标很明确，搜集这样一个通项公式：
从 m×n 网格的左下点(S)到右上点(F)，沿着网线走，有几种走法(网线,格点都不能重复)？
如同帖子《彩珠手串的配色计数》：用 m 种颜色的珠子穿手串，每串有 n 颗珠子，有多少种配色不同的手串？

aimisiyou 发表于 2021-4-20 16:06:55

王守恩 发表于 2021-4-20 15:54
我的目标很明确，搜集这样一个通项公式：
从 m×n 网格的左下点(S)到右上点(F)，沿着网线走，有几种走法 ...
可以通过编写程序来计算F(m,n)，不代表就能得出其显式通项。

aimisiyou 发表于 2021-4-21 14:08:56

mathe 发表于 2021-4-20 12:43
找到答案了
https://bbs.emath.ac.cn/thread-517-1-1.html



除了BFS，难道还有什么其它算法吗？

kastin 发表于 2021-4-21 20:24:01

是这个问题吗？
https://bbs.emath.ac.cn/thread-16151-1-1.html

查看完整版本: 从3×3网格的左下角到右上角有几种走法？