逃离节奏面


Madeline 又遇到她最讨厌的节奏面啦！

节奏面是一个 $n$ 行 $m$ 列的二维网格地图，其中第 $n$ 行为地面。节奏面中存在一些障碍格子，Madeline 不能进入或者穿过它们。

每一秒，节奏面中障碍格子的分布情况会发生变化。节奏面共有 $k$ 种形态，第一秒时，节奏面处于第一种形态，之后每过一秒，节奏面都会变成下一种形态。特殊地，如果当前节奏面处于第 $k$ 种形态，下一秒则会变成第 $1$ 种形态。形式化地讲，节奏面在第 $t$ 秒时处于第 $(t-1)\mod k+1$ 种形态。

**每秒开始时**，Madeline 可以凭借她敏捷的身法进行移动。假设 Madeline 当前位于 $(x,y)$（$(x,y)$ 为位于地图中第 $x$ 行、第 $y$ 列的格子），她的移动将分为两步**依次进行**：

1. 如果 Madeline 在地面上（即 $x=n$），或者脚下有一个障碍格子（即 $(x+1,y)$ 为障碍格子），Madeline 可以选择一个不超过 $h$ 的高度 $u$（$u$ 可以为 $0$），跳跃 $u$ 的高度来到 $(x-u,y)$；否则，Madeline 将下落一格。
2. Madeline 可以向左或者向右移动一格，或者原地不动。

请注意：Madeline 在移动过程中不能进入或者穿过障碍格子且不能移动到地图之外。

**每秒结束时**，节奏面会发生变化，如果此刻 Madeline 位于障碍格子中，她将直接死亡。

Madeline 不想葬生于节奏面中，于是她想寻求你的帮助。第一秒开始时，Madeline 位于地图的右下角（即 $(n,m)$），节奏面的出口位于 $(x,y)$（出口的位置不会发生变化，且地图右下角和出口位置在节奏面的任何形态中都不会是障碍格子）。Madeline 一旦和出口坐标重合，会立刻离开节奏面，她想知道离开节奏面的最早时间。如果无法离开，请输出 $-1$。

测试点包含多组数据。第一行包含一个整数 $T$（$1\leq T\leq 10$），表示数据组数。每组数据的输入格式如下：

第一行包含三个整数 $n$，$m$ 和 $k$（$1\leq n,m\leq 1000$，$1\leq k\leq 5$），分别表示节奏面的行、列和形态数。

接下来若干行，包含 $k$ 个 $n$ 行 $m$ 列的字符矩阵（由 `*` 和 `.` 组成，`*` 表示障碍格子，`.` 表示非障碍格子），分别表示节奏面的每种形态。

接下来一行，包含三个整数 $h$，$x$ 和 $y$（$1\leq h,x\leq n$，$1\leq y\leq m$），分别表示 Madeline 跳跃的最大高度和出口的坐标。保证 $(n,m)$ 和 $(x,y)$ 在节奏面的任何形态中都不是障碍格子。

每组数据包含一个整数，表示离开节奏面的最早时间。如果无法离开，输出 $-1$。

2
3 3 2
.*.
...
...
...
*.*
.*.
1 1 3
2 2 1
.*
*.
2 2 2

2
1

样例共有两组数据：

第一组数据，Madeline 的行动策略如下：

- 第 $1$ 秒：Madeline 向上跳跃 $1$ 格，再向左移动 $1$ 格，到达 $(2,2)$。
- 第 $2$ 秒：Madeline 向上跳跃 $1$ 格，再向右移动 $1$ 格，到达 $(1,3)$（出口位置）。

Madeline 会在第 $2$ 秒离开节奏面。可以证明，Madeline 无法更早离开节奏面。

第二组数据，Madeline 在第 $1$ 秒开始时就位于出口位置，因此可以直接离开。

“华为杯”杭州电子科技大学2023新生编程大赛