#2493. [CSP-J 2024] 地图探险
[CSP-J 2024] 地图探险
题目描述
小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂,为了防止迷路,他先派遣了一个机器人前去探路。
丛林的地图可以用一个 行 列的字符表来表示。我们将第 行第 列的位置的坐标记作 。如果这个位置的字符为 ,即代表这个位置上有障碍,不可通过。反之,若这个位置的字符为 ,即代表这个位置是一片空地,可以通过。
这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 刻画,它表示机器人处在地图上第 行第 列的位置。而朝向用一个 的 整数 表示,其中 代表向东, 代表向南, 代表向西, 代表向北。
初始时,机器人的位置为 ,朝向为 。保证初始时机器人所在的位置为空地。接下来机器人将要进行 次操作。每一步,机器人将按照如下的模式操作:
- 假设机器人当前处在的位置为 ,朝向为 。则它的方向上的下一步的位置 定义如下:若 ,则令 ,若 ,则令 ,若 ,则令 ,若 ,则令 。
- 接下来,机器人判断它下一步的位置是否在地图内,且是否为空地。具体地说,它判断 是否满足 ,且 位置上是空地。如果条件成立,则机器人会向前走一步。它新的位置变为 ,且朝向不变。如果条件不成立,则它会执行“向右转”操作。也就是说,令 (即 除以 的余数),且它所处的位置保持不变,但朝向由 变为 。
小 A 想要知道,在机器人执行完 步操作之后,地图上所有被机器人经过的位置(包括起始位置)有几个。
输入格式
本题有多组测试数据。
输入的第一行包含一个正整数 ,表示数据组数。
接下来包含 组数据,每组数据的格式如下:
第一行包含三个正整数 。其中 表示地图的行数和列数, 表示机器人执行操作的次数。
第二行包含两个正整数 和一个非负整数 。
接下来 行,每行包含一个长度为 的字符串。保证字符串中只包含 和 两个字符。其中,第 行的字符串的第 个字符代表的位置为 。这个位置是 即代表它是障碍,否则代表它是空地。数据保证机器人初始时所在的位置为空地。
输出格式
对于每组数据:输出一行包含一个正整数,表示地图上所有被机器人经过的位置(包括起始位置)的个数。
样例 #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 解释】
该样例包含两组数据。对第一组数据,机器人的状态以如下方式变化:
- 初始时,机器人位于位置 ,方向朝西(用数字 代表)。
- 第一步,机器人发现它下一步的位置 不在地图内,因此,它会执行“向右转”操作。此时,它的位置仍然为 ,但方向朝北(用数字 代表)。
- 第二步,机器人发现它下一步的位置 不在地图内,因此,它仍然会执行“向右转”操作。此时,它的位置仍然为 ,但方向朝东(用数字 代表)。
- 第三步,机器人发现它下一步的位置 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 ,方向仍然朝东。
- 第四步,机器人发现它下一步的位置 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 ,方向仍然朝东。
因此,四步之后,机器人经过的位置有三个,分别为 。
对第二组数据,机器人依次执行的操作指令为:向东走到 ,向东走到 ,向东走到 ,向东走到 ,向右转,向南走到 ,向南走到 ,向南走到 ,向南走到 ,向右转,向西走到 ,向西走到 ,向西走到 ,向右转,向北走到 ,向右转,向右转,向南走到 ,向右转,向右转。
【样例 2】
见选手目录下的 explore/explore2.in 与 explore/explore2.ans。
该样例满足第 个测试点的限制条件。
【样例 3】
见选手目录下的 explore/explore3.in 与 explore/explore3.ans。
该样例满足第 个测试点的限制条件。
【样例 4】
见选手目录下的 explore/explore4.in 与 explore/explore4.ans。
该样例满足第 个测试点的限制条件。
【样例 5】
见选手目录下的 explore/explore5.in 与 explore/explore5.ans。
该样例满足第 个测试点的限制条件。
【数据范围】
对于所有测试数据,保证:,,,,,且机器人的起始位置为空地。
测试点编号 | 特殊性质 | |||
---|---|---|---|---|
无 | ||||
地图上所有位置均为空地 | ||||
无 | ||||
地图上所有位置均为空地 | ||||
无 | ||||
Statistics
Related
In following contests: