A1632.无障碍迷宫

入门

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

AC狗做了一个梦,梦见自己被困在一个无障碍迷宫里(既然无障碍,为什么还叫迷宫?)

这个迷宫是一个 N×MN×M 的方阵,方阵内部每个格子是小房间,AC狗每次只能向下或者向右移动一个房间。方阵的边界是空气墙,AC狗没办法穿过空气墙出去。

AC狗的起点在左上角,出口在右下角。

当AC狗走到出口的时候,出口有一头带树,他会问AC狗从起点到出口一共有多少条路径,AC狗给出正确答案后,带树才会放他出去。

虽然AC狗的智商比肩带树,但是他始终算不清有多少条路,请你帮他计算。

输入格式

输入仅有一行,包含两个正整数,分别代表 NMN、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%的数据,N10M10N≤10,M≤10

对于 100%的数据,N20M20N≤20,M≤20

首页