题目描述：

给定一个大小为 $n \times n$ 的二维网格。你从坐标 $(sx, sy)$ 出发，允许你每次移动到上下左右四个方向之一。每次移动的步数记为 $1$ 步。现在给定一个目标坐标 $(ex, ey)$，请问在最多 $k$ 步以内，你可以到达目标位置 $(ex, ey)$ 的不同路径数。

请注意，你可以在任何时刻选择停止，不一定要在刚好 $k$ 步时到达目标。

输入

• 第一行输入一个整数 $n$，表示网格的大小 $(1 \leq n \leq 10)$。
• 第二行输入四个整数 $sx, sy, ex, ey$，表示起点 $(sx, sy)$ 和终点 $(ex, ey)$ 的坐标 $(1 \leq sx, ex \leq n, 1 \leq sy, ey \leq n)$。
• 第三行输入一个整数 $k$，表示最多的步数 $(1 \leq k \leq 10)$。

输出

• 输出一个整数，表示在最多 $k$ 步以内从 $(sx, sy)$ 到达 $(ex, ey)$ 的不同路径数。

示例

输入

3
1 1 2 2
4

输出

18

【递归5】路径统计②

题面描述

给定一个大小为 $n \times n$ 的二维网格，起点为坐标 $(sx, sy)$，目标位置为 $(ex, ey)$，你可以在网格中上下左右四个方向进行移动，每次移动一步。要求在最多 $k$ 步以内，求从起点到目标位置的不同路径数。请注意，可以在任意时刻选择停止，不一定要在恰好 $k$ 步时到达目标。

思路分析

这是一个典型的递归问题。我们需要计算从起点 $(sx, sy)$ 到终点 $(ex, ey)$ 的所有可能路径数，且路径步数不超过 $k$。每一步可以向上下左右四个方向移动。

1. 偏移量数组讲解：

我们可以用两个数组来表示在 $x$ 轴和 $y$ 轴上的移动变化，分别表示上下左右四个方向的偏移量。

# 四个方向：上、下、左、右
dx = [-1, 1, 0, 0]  # x轴的变化量
dy = [0, 0, -1, 1]  # y轴的变化量

• dx 数组表示在 $x$ 轴上的移动变化：

  • -1：向上移动（$x$减1）
  • 1：向下移动（$x$加1）
  • 0：不在 $x$ 轴方向移动
  • 0：不在 $x$ 轴方向移动

• dy 数组表示在 $y$ 轴上的移动变化：

  • 0：不在 $y$ 轴方向移动
  • 0：不在 $y$ 轴方向移动
  • -1：向左移动（$y$减1）
  • 1：向右移动（$y$加1）

通过这两个数组，可以方便地遍历所有四个方向的移动。

2. 递归终止条件：

• 到达终点：如果当前位置等于终点 $(ex, ey)$，我们就找到了一个有效路径，计数加一。

# 如果当前坐标是终点，则计数加一
if x == ex and y == ey:
    countPaths += 1
    # 继续递归，因为可以选择继续移动直到步数达到 k

• 到达最大步数：如果已经移动的步数达到 $k$，就停止递归。

# 如果已经达到最大步数，停止递归
if steps == k:
    return

3. 递归过程：

• 从当前位置开始，尝试向四个方向移动，每移动一步，步数加一，然后递归调用。

# 尝试四个方向移动
for dir in range(4):
    newX = x + dx[dir]
    newY = y + dy[dir]
    # 检查新位置是否在网格内
    if 1 <= newX <= n and 1 <= newY <= n:
        dfs(newX, newY, steps + 1, n, sx, sy, ex, ey, k)

• 需要确保新位置不越界，即 $1 \leq \text{newX} \leq n$ 且 $1 \leq \text{newY} \leq n$。

4. 计数：

• 每当递归到达终点时，不论当前步数是否等于 $k$，都会计数，因为我们可以选择在到达终点后继续移动，直到步数达到最大步数。

时间复杂度

递归的时间复杂度是指数级的。最坏情况下，递归树的深度为 $k$，每个节点有 4 个子节点，因此递归的时间复杂度为 O(4^k)。

但是，由于可以选择停止，实际执行的递归次数可能会少得多。

Python代码实现

# 定义全局变量
countPaths = 0  # 记录路径数

# 四个方向：上，下，左，右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

# 递归函数，当前坐标 (x, y)，已经走的步数 steps
def dfs(x, y, steps, n, sx, sy, ex, ey, k):
    global countPaths
    
    # 如果当前坐标是终点，则计数加一
    if x == ex and y == ey:
        countPaths += 1
    
    # 如果已经达到最大步数，停止递归
    if steps == k:
        return
    
    # 尝试四个方向移动
    for dir in range(4):
        newX = x + dx[dir]
        newY = y + dy[dir]
        # 检查新位置是否在网格内
        if 1 <= newX <= n and 1 <= newY <= n:
            dfs(newX, newY, steps + 1, n, sx, sy, ex, ey, k)

# 主函数
if __name__ == "__main__":
    # 输入
    n = int(input())  # 网格大小
    sx, sy, ex, ey = map(int, input().split())  # 起点和终点 (sx, sy, ex, ey)
    k = int(input())  # 最大步数
    
    # 开始递归，初始步数为 0
    dfs(sx, sy, 0, n, sx, sy, ex, ey, k)
    
    # 输出结果
    print(countPaths)