地图探险

题目描述

小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂，为了防止迷路，他先派遣了一个机器人前去探路。

丛林的地图可以用一个 n 行 m 列的字符表来表示。我们将第 i 行第 j 列的位置的坐标记作 (i, j) (1 <= i <= n, 1 <= j <= m)。如果这个位置的字符为 x，即代表这个位置上有障碍，不可通过。反之，若这个位置的字符为 .，即代表这个位置是一片空地，可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 (x, y) (1 <= x <= n, 1 <= y <= m) 刻画，它表示机器人处在地图上第 x 行第 y 列的位置。而朝向用一个 0 到 3 的整数 d 表示，其中 d = 0 代表向东，d = 1 代表向南，d = 2 代表向西，d = 3 代表向北。

初始时，机器人的位置为 (x0, y0)，朝向为 d0。保证初始时机器人所在的位置为空地。接下来机器人将要进行 k 次操作。每一步，机器人将按照如下的模式操作：

1. 假设机器人当前处在的位置为 (x, y)，朝向为 d。则它的方向上的下一步的位置 (x', y') 定义如下：若 d = 0，则令 (x', y') = (x, y + 1)，若 d = 1，则令 (x', y') = (x + 1, y)，若 d = 2，则令 (x', y') = (x, y - 1)，若 d = 3，则令 (x', y') = (x - 1, y)。

2. 接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断 (x', y') 是否满足 1 <= x' <= n, 1 <= y' <= m，且 (x', y') 位置上是空地。如果条件成立，则机器人会向前走一步。它新的位置变为 (x', y')，且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令 d' = (d + 1) mod 4（即 d + 1 除以 4 的余数），且它所处的位置保持不变，但朝向由 d 变为 d'。

小 A 想要知道，在机器人执行完 k 步操作之后，地图上所有被机器人经过的位置（包括起始位置）有几个。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 T，表示数据组数。

接下来包含 T 组数据，每组数据的格式如下：

第一行包含三个正整数 n, m, k。其中 n, m 表示地图的行数和列数，k 表示机器人执行操作的次数。

第二行包含两个正整数 x0, y0 和一个非负整数 d0。

接下来 n 行，每行包含一个长度为 m 的字符串。保证字符串中只包含 x 和 . 两个字符。其中，第 x 行的字符串的第 y 个字符代表的位置为 (x, y)。这个位置是 x 即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。

输出格式

对于每组数据：输出一行包含一个正整数，表示地图上所有被机器人经过的位置（包括起始位置）的个数。

样例 #1

输入 #1

2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....

输出 #1

3
13

数据范围

对于所有测试数据，保证：1 <= T <= 5，1 <= n, m <= 10^3，1 <= k <= 10^6，1 <= x0 <= n，1 <= y0 <= m，0 <= d0 <= 3，且机器人的起始位置为空地。