题目描述

在一个 n×m 的棋盘上，给定一个起点 (r, c) 和一个步数 k。马（骑士）按照国际象棋规则移动（走日字），每次必须恰好走一步。问马在恰好走 k 步后，有多少个不同的格子可以到达。

输入格式

一行四个整数 n, m, r, c, k（1 ≤ n, m ≤ 10, 0 ≤ r < n, 0 ≤ c < m, 0 ≤ k ≤ 10），分别表示棋盘大小、起点坐标和步数。 坐标从 0 开始，(0, 0) 为左上角。

输出格式

一个整数，表示恰走 k 步后能到达的不同格子数。

样例输入 1

3 3 1 1 1

样例输出 1

0

样例输入 2

5 5 2 2 1

样例输出 2

8

提示

使用 DFS 深度搜索 k 步，记录终点位置。注意：同一个格子可能在多种路径下被到达，需要用集合去重。