2D 网格游戏

2D Grid Game

专题: Discrete Math / 离散数学
难度: L4
来源: OpenQuant

第 1 小问

题目详情

你正在玩一款 2D 游戏，你的角色被困在 6×6 网格内。你的角色从标记为 (1, 1) 的网格左上角开始，只能向右和向下移动。

第 1 部分

你的角色可以采取多少条可能的路径到达标记为 (6,6) 的网格的右下角？

You are playing a 2D game where your character is trapped within a 6×6 grid. Your character starts at the top left corner of the grid marked (1, 1) and can only move right and down.

Part 1

How many possible paths can your character take to get to the bottom right of the grid marked (6,6)?

解析

在这个问题中需要注意的关键观察是，对于从右上角索引 (1, 1) 到右下角 (6,6) 的每条有效路径，有 5 次必要的“向右”移动和 5 次必要的“向下”移动，总共 10 次移动。这意味着从开始到结束的每条有效路径恰好有 10 步，其中 5 步是正确的，5 步是向下的。你选择向右和向下移动的 $\textit{order}$ 会导致不同的路径。

在总共 10 个步骤中，有 $\dbinom{10}{5}$ 方法来选择“右”移动，以及对称的 $\dbinom{10}{5}$ 方法来选择“下”移动。此计算的结果得出将 10 次移动中的 5 次排列为向下或向右的方式数。对于此问题，选择向右移动的方式数量和向下移动的方式数量是对称的，并得出答案 252。

Original Explanation

The key observation to note in this problem is that for every valid path from the top right index (1, 1) to the bottom right (6,6), there are 5 necessary 'right' movements, and 5 necessary 'down' movements, for an exact total of 10 movements. This means that every valid path from start to finish has exactly 10 moves, 5 of which are right, and 5 of which are down. The $\textit{order}$ in which you choose the right and down moves is what results in different paths.

Of the 10 total steps, there are $\dbinom{10}{5}$ ways to select 'right' moves, and symmetrically $\dbinom{10}{5}$ ways to select 'down' moves. The result of this calculation yields the number of ways to arrange 5 of the 10 moves as either down or right. Choosing the number of ways to move right, and the number of ways to move down is symmetrical for this problem, and yields the answer 252.

第 2 小问

题目详情

你正在玩一款 2D 游戏，你的角色被困在 6×6 网格内。你的角色从标记为 (1, 1) 的网格左上角开始，只能向右和向下移动。

第 2 部分

你能编写一个算法来解决任意 $N$ by $M$ 维度网格的问题吗？

You are playing a 2D game where your character is trapped within a 6×6 grid. Your character starts at the top left corner of the grid marked (1, 1) and can only move right and down.

Part 2

Can you write an algorithm to solve this for an arbitrary $N$ by $M$ dimension grid?

解析

我们可以应用与第一部分类似的方法来得到 $\dbinom{N+M-2}{M-1}$ = $\dbinom{N+M-2}{N-1}$ 。 $\textit{N + M - 2}$ 源于我们从 [1, 1] 索引开始的事实，这意味着只有 $\textit{N-1}$ 向下步进，并且只有 $\textit{M-1}$ 向右步进。然后，我们将这两项加在一起以获得可能的移动总数，并从该总数中选择 $\textit{M-1}$ 或 $\textit{N-1}$ 定向移动。

下面是我们刚刚描述的过程的 python 实现

def count_ways(n: int, m: int) -> int:
   """
   Find the number of ways to reach (n, m) starting at (0, 0)
   """
   grid = [[0] * m for _ in range(n)]

   for row in range(n):
      for col in range(m):
         if row == 0 or col == 0:
            grid[row][col] = 1; continue

         grid[row][col] = grid[row-1][col] + grid[row][col-1]

   return grid[-1][-1]

Original Explanation

We can apply a similar methodology from the first part to get $\dbinom{N+M-2}{M-1}$ = $\dbinom{N+M-2}{N-1}$ . The $\textit{N + M - 2}$ stems from the facts that we are beginning at the [1, 1] index, meaning there are only $\textit{N-1}$ steps down, and only $\textit{M-1}$ steps to the right. We then add these two terms together to get our total possible moves, and choose either $\textit{M-1}$ or $\textit{N-1}$ directional moves from this total.

Below is a python implementation of the process we just described

def count_ways(n: int, m: int) -> int:
   """
   Find the number of ways to reach (n, m) starting at (0, 0)
   """
   grid = [[0] * m for _ in range(n)]

   for row in range(n):
      for col in range(m):
         if row == 0 or col == 0:
            grid[row][col] = 1; continue

         grid[row][col] = grid[row-1][col] + grid[row][col-1]

   return grid[-1][-1]