返回题库

12×12 网格路径数

Walking on a Grid

专题
Algorithmic Programming / 算法编程
难度
L2

题目详情

从 12×1212\times12 方格的左下角走到右上角，每一步只能向右或向上。问共有多少条不同路径？

You start at the bottom-left corner of a 12×1212 \times 12 grid and want to reach the top-right corner. At each step, you can either move right or move up. How many distinct paths can you take to reach the top-right corner?

解析

一共需要走 24 步，其中向右 12 步、向上 12 步。

不同路径数等于在 24 个位置中选出 12 个位置放“向上”的方式数：

(2412)=24!12! 12!=2,704,156.\binom{24}{12}=\frac{24!}{12!\,12!}=2{,}704{,}156.

Original Explanation

To move from the bottom-left to the top-right corner of a 12×1212 \times 12 grid, you must make exactly 12 right moves (R) and 12 up moves (U), for a total of 24 moves. The problem becomes: In how many ways can you arrange a sequence with 12 R's and 12 U's?

This is a classic combinations problem. The number of such sequences is given by the number of ways to choose 12 positions for U (or R) out of 24 total moves:

(2412)=24!12!⋅12!\binom{24}{12} = \frac{24!}{12! \cdot 12!}

Computing this gives:

(2412)=2, ⁣704, ⁣156\binom{24}{12} = 2,\!704,\!156

So, there are 2,704,156 distinct paths from the bottom-left to the top-right corner.