作者mantour (朱子)
看板Math
标题Re: [排组] 一题限制转弯次数的捷径问题
时间Sun Apr 9 23:30:55 2017
※ 引述《wayne0824 (莱恩)》之铭言:
: http://i.imgur.com/iXwDeqB.jpg
: 如题,除了要讨论在P以前和P以後的转弯次数,还要考虑在P点是否有转弯 想请问各位有其他想法吗?
: 题目出自高雄女中补充教材
: -----
: Sent from JPTT on my iPhone
对每一点Q(x,y)定义一个2x5矩阵 M(x,y,i,j), i=1~2, j=0~4
M(x,y,1,j) = 到达该点刚好转j次,且最後一步向右的走法数
M(x,y,2,j) = 到达该点刚好转j此,且最後一步向上的走法数
则有以下关系
M(x,y,1,j) = 到达 Q'(x-1,y) 刚好转j次,且最後一步向右的走法数
+到达 Q'(x-1,y) 刚好转j-1次,且最後一步向上的走法数
= M(x-1,y,1,j) + M(x-1,y,2,j-1)
同理
M(x,y,2,j) = M(x,y-1,1,j-1) + M(x,y-1,2,j)
以上二式叠代从左下角开始往右上角填上各点的矩阵,注意在禁止路径上的各点值皆为0
可得下图
http://imgur.com/a/Qionh
得解从A经过P到达B走捷径
刚好转2次有 1+1 = 2 种走法
刚好转3次有 5+5 = 10种走法
刚好转4次有 19+13 = 32种走法
这个解法有点类似演算法里面的动态规划
可以同时一次解出B点以外到达各点,转不同次数的走法数
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.225.221.208
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1491751859.A.DF3.html
※ 编辑: mantour (36.225.221.208), 04/09/2017 23:35:22
1F:推 Desperato : 推推 04/09 23:41