【递归5】路径统计②

题解

题面描述

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

思路

题目描述：

给定一个大小为 $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