#10000014. 【CSP-J 2024】地图探险（explore）

提交源程序文件名

【题目描述】

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

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

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 （，) 刻画，它表示机器人处在地图上第 行第 列的位置。而朝向用一个 的整数 表示，其中 代表向东， 代表向南， 代表向西， 代表向北。

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

1. 假设机器人当前处在的位置为 ，朝向为 。则它的方向上的下一步的位 置 定义如下：若 ，则令 ，若 ，则令 ，若 ，则令 ，若 ，则令 。
2. 接下来，机器人判断它下一步的位置是否在地图内，且是否为空地。具体地说，它判断 是否满足 ，，且 位置上是空地。如果条件成立，则机器人会向前走一步。它新的位置变为 ，且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令 （即 除以 的余数），且它所处的位置保持不变，但朝向由 变为 。

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

【输入格式】

从文件 中读入数据。

本题有多组测试数据。

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

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

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

第二行包含两个正整数 和一个非负整数 。

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

【输出格式】

输出到文件 中。

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

【样例 输入】

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

【样例 输出】

3
13

【样例 解释】

该样例包含两组数据。对第一组数据，机器人的状态以如下方式变化：

1. 初始时，机器人位于位置 ，方向朝西（用数字 代表）。
2. 第一步，机器人发现它下一步的位置 不在地图内，因此，它会执行“向右转”操作。此时，它的位置仍然为 ，但方向朝北（用数字 代表）。
3. 第二步，机器人发现它下一步的位置 不在地图内，因此，它仍然会执行“向右转”操作。此时，它的位置仍然为 ，但方向朝东（用数字 代表）。
4. 第三步，机器人发现它下一步的位置 在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为 ，方向仍然朝东。
5. 第四步，机器人发现它下一步的位置 在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为 ，方向仍然朝东。

因此，四步之后，机器人经过的位置有三个，分别为 。

对第二组数据，机器人依次执行的操作指令为：向东走到 ，向东走到 ，向东走到 ，向东走到 ，向右转，向南走到 ，向南走到 ，向南走到 ，向南走到 ，向右转，向西走到 ，向西走到 ，向西走到 ，向右转，向北走到 ，向右转，向右转，向南走到 ，向右转，向右转。

【样例 】

见选手目录下的 与 。

该样例满足第 个测试点的限制条件。

【样例 】

见选手目录下的 与 。

该样例满足第 个测试点的限制条件。

【样例 】

见选手目录下的 与 。

该样例满足第 个测试点的限制条件。

【样例 】

见选手目录下的 与 。

该样例满足第 个测试点的限制条件。

【数据范围】

对于所有测试数据，保证：，且机器人的起始位置为空地。