题目描述
首先我们回忆一下经典难题过河卒问题:
棋盘上 $A$ 点有一个过河卒,需要走到目标 $B$ 点。卒行走的规则:可以向上、或者向右。同时在棋盘上 $C$ 点有一个对方的马,该马所在的点和所有跳跃一步可达的点称为对方马的控制点,因此称之为「马拦过河卒」。
棋盘用坐标表示,$A$ 点 $(1,1)$ 、$B$ 点 $(N,M)$ ,同样马的位置坐标是需要给出的。
现在要求你计算出卒从 $A$ 点能够到达 $B$ 点的路径的条数,假设马的位置是固定不动的,并不是卒走一步马走一步。
请注意,上述背景内容与本题无关!
Kiana 喜欢玩象棋,尤其是喜欢用象棋玩过河卒的游戏。在传统的过河卒问题中,Kiana 需要控制一个卒从起点走到终点,在路中避开一个对方的马的攻击,然后假装不会算并询问你从起点到终点的路径总数。
在今天的过河卒二游戏中,Kiana 还是控制一个卒在一个 $N\times M$ 的棋盘上移动,初始时卒位于左下方坐标为 $(1,1)$ 位置,但为了增加难度,Kiana 对游戏规则做出了一些修改。传统的过河卒每步只能向上或向右移动 $1$ 格,Kiana 规定自己的过河卒二还可以在一步中向右上方移动 $1$ 格,即如果当前卒位于坐标 $(x,y)$ 处,则下一步可以走到 $(x+1,y)$ 、$(x,y+1)$ 或 $(x+1,y+1)$ 中的任意一格里面去,同时 Kiana 认为,如果两种移动方案在某一步时卒移动的方向(右、上或右上)不同,则两种方案就是不同的,例如从 $(1,1)$ 先走到 $(1,2)$ 再走到 $(2,2)$ 、从 $(1,1)$ 先走到 $(2,1)$ 再走到 $(2,2)$ 和从 $(1,1)$ 直接走到 $(2,2)$ 是三种不同的移动方案。
其次,过河卒二的终点不再是一个特定的位置,Kiana 规定卒可以从棋盘的上方或右方走出棋盘,此时就视为游戏成功。注意在走出棋盘时仍然有方向选择的不同,例如若过河卒位于 $(1,M)$ 处,则下一步它可以向右或者向右上用两种方式走出棋盘,若过河卒位于 $(N,M)$ 处,则下一步它可以向上、向右或者向右上用三种方式走出棋盘,以不同的方式走出棋盘仍然被算作是不同的移动方案。