2024 CSP-J 第二轮 T2｜地图探险

一、完整题目

丛林地图用一个 n 行 m 列的字符表表示。第 i 行第 j 列的坐标记作 (i,j)，其中 1≤i≤n，1≤j≤m。

• 字符为 x：该位置有障碍，不可通过；
• 字符为 .：该位置是空地，可以通过。

机器人的状态由位置 (x,y) 和朝向 d 组成。朝向用 0～3 表示：

初始时，机器人在 (x₀,y₀)，朝向为 d₀，且起始位置保证是空地。接下来它执行 k 次操作。每次操作都按以下规则进行：

1. 根据当前朝向计算正前方的下一格 (x′,y′)。
2. 若 (x′,y′) 在地图内，且是空地，机器人向前走到该格，朝向不变。
3. 否则，机器人只向右转，位置不变，新朝向为 (d+1) mod 4。

求机器人执行完 k 次操作后，一共经过了多少个不同的位置，起始位置也要计入。

输入格式

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

本题有多组测试数据。输入第一行包含一个正整数 T，表示数据组数。

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

• 第一行包含三个正整数 n,m,k，表示地图行数、列数和操作次数。
• 第二行包含两个正整数 x₀,y₀ 和一个非负整数 d₀。
• 接下来 n 行，每行一个长度为 m 的字符串，仅包含 x 和 .。第 x 行字符串的第 y 个字符表示坐标 (x,y)。

数据保证机器人的起始位置是空地。

输出格式

输出到文件 explore.out 中。

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

样例 1

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

3
13

样例 1 说明

第一组数据中，机器人初始在 (1,1) 且朝西。前两步的正前方分别是 (1,0) 和 (0,1)，均越界，因此两步都只向右转；第三、四步依次走到 (1,2) 和 (1,3)。经过的不同位置为 (1,1),(1,2),(1,3)，答案为 3。

第二组数据的 20 次操作依次为：东走 4 格、右转、南走 4 格、右转、西走 3 格、右转、北走 1 格、右转、右转、南走 1 格、右转、右转，共经过 13 个不同位置。

其余大样例随试题资料提供：样例 2 对应测试点 3～4，样例 3 对应测试点 5，样例 4 对应测试点 6，样例 5 对应测试点 8～10。

数据范围与测试点

对于所有测试数据：1≤T≤5，1≤n,m≤10³，1≤k≤10⁶，1≤x₀≤n，1≤y₀≤m，0≤d₀≤3，且起始位置为空地。