邮递员路线问题：计算最短路径方案数

邮递员路线问题：计算最短路径方案数

小李在 P 市的邮政局工作，他每天的工作是从邮局出发，到自己所管辖的所有邮筒取信件，然后带回邮局。他所管辖的邮筒非常巧地排成了一个 m×n 的点阵（点阵中的间距都是相等的）。左上角的邮筒恰好在邮局的门口。

小李是一个非常标新立异的人，他希望每天都能走不同的路线，但是同时，他又不希望路线的长度增加（即选择最短的路径走，注意路径长度是指小李实际走的物理距离，并且对路过每个邮筒的次数没有限制），他想知道他有多少条不同的路线可走。他在任何两个邮筒之间走的是直线。

思路

首先，我们可以发现，对于一个 m×n 的点阵，小李每次只能向右或向下走，因此他总共需要走 m+n-2 步，其中向右走的步数为 n-1，向下走的步数为 m-1。

其次，对于每一条路径，小李需要向右走 n-1 步，向下走 m-1 步，因此他实际上需要在这 m+n-2 步中选择 n-1 步向右走，其余步数向下走。

因此，答案就是从 m+n-2 步中选择 n-1 步的方案数，即组合数 C(m+n-2, n-1)。

代码实现

import math

m, n = map(int, input().split())

ans = math.comb(m+n-2, n-1)

print(ans)