地图探险（explore）

本题为 CSP-J 2024 第二轮真题。本 OJ 采用标准输入输出评测，无需文件重定向。

【题目描述】 小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 步操作之后，地图上所有被机器人经过的位置 （包括起始位置）有几个。 【输入格式】 从文件explore.in 中读入数据。 .本.题.有.多.组.测.试.数.据。 输入的第一行包含一个正整数T，表示数据组数。 接下来包含T 组数据，每组数据的格式如下： 第一行包含三个正整数n, m, k。其中n, m 表示地图的行数和列数，k 表示机器人 执行操作的次数。 第二行包含两个正整数x0, y0 和一个非负整数d0。 接下来n 行，每行包含一个长度为m 的字符串。保证字符串中只包含x 和. 两个 字符。其中，第x 行的字符串的第y 个字符代表的位置为(x, y)。这个位置是x 即代表 它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。 【输出格式】 输出到文件explore.out 中。 对于每组数据：输出一行包含一个正整数，表示地图上所有被机器人经过的位置 （包括起始位置）的个数。 【样例1 输入】 1 2 2 1 5 4 3 1 1 2 4 ....x 5 5 5 20 6 1 1 0 7 ..... 8 .xxx. 9 .x.x. 10 ..xx. 11 x.... 【样例1 输出】 1 3 2 13 【样例1 解释】 该样例包含两组数据。对第一组数据，机器人的状态以如下方式变化：
3. 初始时，机器人位于位置(1, 1)，方向朝西（用数字2 代表）。
4. 第一步，机器人发现它下一步的位置(1, 0) 不在地图内，因此，它会执行“向右 转”操作。此时，它的位置仍然为(1, 1)，但方向朝北（用数字3 代表）。
5. 第二步，机器人发现它下一步的位置(0, 1) 不在地图内，因此，它仍然会执行“向 右转”操作。此时，它的位置仍然为(1, 1)，但方向朝东（用数字0 代表）。
6. 第三步，机器人发现它下一步的位置(1, 2) 在地图内，且为空地。因此，它会向 东走一步。此时，它的位置变为(1, 2)，方向仍然朝东。
7. 第四步，机器人发现它下一步的位置(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，且机器人的起始位置为空地。 测试点编号 n m k 特殊性质 1 = 1 ≤2 = 1 无 2 3 ≤102 ≤102 4 5 = 1 ≤103 ≤2 · 103 地图上所有位置均为空地 6 无 7 ≤103 ≤106 地图上所有位置均为空地 8 无 9 10

小木棍（sticks） 小木棍（sticks）

📦 本题含官方测试数据（CC BY-NC，noi.cn 发布），共 10 个测试点。