2024 CCF 非专业级软件能力认证 CSP-J/S 2024 第二轮认证
入门级 地图探险(explore)
地图探险(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 代表向北。
初始时,机器人的位置为 (x
0
, y
0
),朝向为 d
0
。
.
保
.
证
.
初
.
始
.
时
.
机
.
器
.
人
.
所
.
在
.
的
.
位
.
置
.
为
.
空
.
地。接下来机器人将要进行 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 表示机器人
执行操作的次数。
第二行包含两个正整数 x
0
, y
0
和一个非负整数 d
0
。
接下来 n 行,每行包含一个长度为 m 的字符串。保证字符串中只包含 x 和 . 两个
字符。其中,第 x 行的字符串的第 y 个字符代表的位置为 (x, y)。这个位置是 x 即代表
它是障碍,否则代表它是空地。数据保证机器人初始时所在的位置为空地。
第 5 页 共 14 页