2718:移动路线（动态规划）

2718:移动路线

总时间限制: 1000ms 内存限制: 65536kB
描述
×桌面上存在一个由m行n列组成的方格矩阵，每个方格均可通过坐标进行标识，其中行坐标自下而上依次增加，列坐标自左向右依次增加，左下角的方格坐标为(1,1)，那么右上角的方格坐标则为(m,n)。
小明是一个活泼好动的孩子，某日他捕捉到一只蚂蚁，不慎将其右脚弄伤，导致该蚂蚁只能选择向上或向右两个方向移动。他将这只蚂蚁放置于左下角的方格中，要求蚂蚁从该位置出发，最终抵达右上角的方格。每一步移动仅限于一个方格。在整个移动过程中，蚂蚁始终处于该方格矩阵内部，请计算所有可能的不同移动路径数量。
当矩阵仅包含1行1列时，蚂蚁无需移动即可完成任务，此时路径数目为1；若矩阵为1行2列（或2行1列），蚂蚁只需进行一次向右（或向上）的移动即可到达终点，此时路径数目同样为1……对于一个2行3列的方格矩阵而言，其具体布局如图所示：

|(2,1)|(2,2)|(2,3)|

|(1,1)|(1,2)|(1,3)|

蚂蚁存在三种行进路径：
路径一：(1,1) → (1,2) → (1,3) → (2,3)
路径二：(1,1) → (1,2) → (2,2) → (2,3)
路径三：(1,1) → (2,1) → (2,2) → (2,3)
输入数据