地图探险(explore)

题目描述

小 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次操作。每一步，机器人将按照如下的模式操作:

假设机器人当前处在的位置为 (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)。

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

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

输入格式

从文件 explore.in 中读入数据。

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

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

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

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

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

输出格式

输出到文件 explore.out 中。

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

样例 1 输入

2

1 5 4 

1 1 2

....x

5 5 20

1 1 0

.....

.xxx.

.x.x.

..xx.

x....

样例 1 输出 

3

13

样例 1 解释

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

1、初始时，机器人位于位置 (1, 1)，方向朝西(用数字 2 代表)。

2、第一步，机器人发现它下一步的位置 (1, 0) 不在地图内，因此，它会执行“向右转”操作。此时，它的位置仍然为 (1, 1)，但方向朝北(用数字 3 代表)。

3、第二步，机器人发现它下一步的位置 (0, 1) 不在地图内，因此，它仍然会执行“向右转”操作。此时，它的位置仍然为 (1, 1)，但方向朝东(用数字 0 代表)。

4、第三步，机器人发现它下一步的位置 (1, 2) 在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为 (1, 2)，方向仍然朝东。

5、第四步，机器人发现它下一步的位置 (1, 3) 在地图内，且为空地。因此，它会向东走一步。此时，它的位置变为 (1, 3)，方向仍然朝东。

因此，四步之后，机器人经过的位置有三个，分别为 (1, 1), (1, 2), (1, 3)。

对第二组数据，机器人依次执行的操作指令为:向东走到 (1, 2)，向东走到 (1, 3)， 向东走到 (1, 4)，向东走到 (1, 5)，向右转，向南走到 (2, 5)，向南走到 (3, 5)，向南走到 (4, 5)，向南走到 (5, 5)，向右转，向西走到 (5, 4)，向西走到 (5, 3)，向西走到 (5, 2)，向 右转，向北走到 (4, 2)，向右转，向右转，向南走到 (5, 2)，向右转，向右转。

样例 2

见选手目录下的 explore/explore2.in 与 explore/explore2.ans。

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

样例 3

见选手目录下的 explore/explore3.in 与 explore/explore3.ans。 该样例满足第 5 个测试点的限制条件。

样例 4

见选手目录下的 explore/explore4.in 与 explore/explore4.ans。

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

样例 5

见选手目录下的 explore/explore5.in 与 explore/explore5.ans。 该样例满足第 8 ∼ 10 个测试点的限制条件。

数据范围

对于所有测试数据，保证:1≤T ≤5,1≤n,m≤103,1≤k≤106,1≤x0 ≤n,1≤ y0 ≤ m, 0 ≤ d0 ≤ 3，且机器人的起始位置为空地。