题意
棋盘上,棋子卒过河后,能够左,右,前移动,棋子马可以控制8个位置+1个位置(本身),从当前位置走到指定的B(m,n)位置,共有多少种走法?
分析过程
从当前位置出发,走到B位置,只能从上面走下来,或者从左边过来。所以,这个就可以使用递推的思想,要想走到(i,j)的位置,只能从(i-1,j)的位置或者(i,j-1)的位置走过来这两种情况,以此类推,有递推式
$f(i,j)=f(i-1,j)+f(i,j-1)$
需要注意的是:如果行进路上有棋子马能够控制,则到达此处的步数为0(即不可到达)
递推代码如下:
1 | for(int i=1; i<=m; i++) |
边界为:要初始化第0行和第0列(i-1,j-1),在处理边界的过程中,我们根据马控制的点来做初始化,如果第一行或者第一列有,就为1,否则就为0。还有f[0][0]处的初始值为1。初始化代码如下:
1 | ok[x][y]=1; |
代码
1 | ok[x][y]=1; |