数学研发论坛

 找回密码
 欢迎注册
查看: 415|回复: 24

[求助] 从3×3网格的左下角到右上角有几种走法?

[复制链接]
发表于 2021-4-18 09:41:16 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
从3×3网格的左下角点到右上角点有几种走法?每个格点最多经过1次。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-19 09:04:43 | 显示全部楼层
BFS。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
回复

使用道具 举报

发表于 2021-4-19 09:44:28 | 显示全部楼层
高中时期的一个经典问题,老师教我们用各种方法来转化这个问题。
印象最深的方法还是递推法。
到达点(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`.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-19 15:56:42 | 显示全部楼层
应该是12种
3X3路线.png
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-20 12:43:18 | 显示全部楼层

评分

参与人数 1威望 +12 金币 +12 贡献 +12 经验 +12 鲜花 +12 收起 理由
王守恩 + 12 + 12 + 12 + 12 + 12 很给力!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-20 13:58:40 | 显示全部楼层

3×3网格

3X3网格是下图右所示吧。
3d633320853a20e4.png
那么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 颗珠子,有多少种配色不同的手串?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-20 16:06:55 | 显示全部楼层
王守恩 发表于 2021-4-20 15:54
我的目标很明确,搜集这样一个通项公式:
从 m×n 网格的左下点(S)到右上点(F),沿着网线走,有几种走法 ...

可以通过编写程序来计算F(m,n),不代表就能得出其显式通项。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-21 14:08:56 | 显示全部楼层
mathe 发表于 2021-4-20 12:43
找到答案了
https://bbs.emath.ac.cn/thread-517-1-1.html

除了BFS,难道还有什么其它算法吗?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2021-4-21 20:24:01 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-5-14 15:37 , Processed in 0.067304 second(s), 23 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表