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

王守恩

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

aimisiyou

BFS。

hujunhua

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

mathe

应该是12种

mathe

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

aimisiyou

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

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

王守恩

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

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

aimisiyou

王守恩 发表于 2021-4-20 15:54
我的目标很明确，搜集这样一个通项公式：
从 m×n 网格的左下点(S)到右上点(F)，沿着网线走，有几种走法 ...

可以通过编写程序来计算F(m,n)，不代表就能得出其显式通项。

aimisiyou

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

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

kastin

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