A1632.无障碍迷宫
入门
官方
通过率:0%
时间限制:1.00s
内存限制:128MB
题目描述
AC狗做了一个梦,梦见自己被困在一个无障碍迷宫里(既然无障碍,为什么还叫迷宫?)
这个迷宫是一个 N×M 的方阵,方阵内部每个格子是小房间,AC狗每次只能向下或者向右移动一个房间。方阵的边界是空气墙,AC狗没办法穿过空气墙出去。
AC狗的起点在左上角,出口在右下角。
当AC狗走到出口的时候,出口有一头带树,他会问AC狗从起点到出口一共有多少条路径,AC狗给出正确答案后,带树才会放他出去。
虽然AC狗的智商比肩带树,但是他始终算不清有多少条路,请你帮他计算。
输入格式
输入仅有一行,包含两个正整数,分别代表 N、M。
输出格式
输出仅有一行,包含一个正整数,表示不同路径的数量。
输入输出样例
输入#1
3 3
输出#1
6
说明/提示
【样例解释】
路径 1:(1,1)——(1,2)——(1,3)——(2,3)——(3,3)
路径 2:(1,1)——(1,2)——(2,2)——(2,3)——(3,3)
路径 3:(1,1)——(1,2)——(2,2)——(3,2)——(3,3)
路径 4:(1,1)——(2,1)——(2,2)——(2,3)——(3,3)
路径 5:(1,1)——(2,1)——(2,2)——(3,2)——(3,3)
路径 6:(1,1)——(2,1)——(3,1)——(3,2)——(3,3)
【数据规模】
对于 50%的数据,N≤10,M≤10。
对于 100%的数据,N≤20,M≤20。