A1412 | 无障碍迷宫
来源官方 / 2023
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
AC狗做了一个梦，梦见自己被困在一个无障碍迷宫里（既然无障碍，为什么还叫迷宫？）
这个迷宫是一个 $N×M$ 的方阵，方阵内部每个格子是小房间，AC狗每次只能向下或者向右移动一个房间。方阵的边界是空气墙，AC狗没办法穿过空气墙出去。
AC狗的起点在左上角，出口在右下角，起点和出口不会是同一个位置。
当AC狗走到出口的时候，出口有一头带树，他会问AC狗从起点到出口一共有多少条路径，AC狗给出正确答案后，带树才会放他出去。
虽然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$。
路径 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$。
C++ 编辑器
输入
输出
可保存默认模板；新题优先使用已保存模板。
当前快捷键仅展示，暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好，我是作答助手。可以问思路、复杂度、样例含义或代码报错原因；不会直接给出完整 AC 代码。
确定要清空代码吗？