#1889. [CSP-J 2024] 地图探险

[CSP-J 2024] 地图探险

题目描述

小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂,为了防止迷路,他先派遣了一个机器人前去探路。

丛林的地图可以用一个 nn 行 mm 列的字符表来表示。我们将第 ii 行第 jj 列的位置的坐标记作 (i,j)(1≤i≤n(i, j)(1 \leq i \leq n,1≤j≤m)1 \leq j \leq m)。如果这个位置的字符为 x\tt x,即代表这个位置上有障碍,不可通过。反之,若这个位置的字符为 .\tt.,即代表这个位置是一片空地,可以通过。

这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 (x,y)(1≤x≤n(x, y)(1 \leq x \leq n,1≤y≤m)1 \leq y \leq m) 刻画,它表示机器人处在地图上第 xx 行第 yy 列的位置。而朝向用一个 0∼30 \sim 3 的整数 dd 表示,其中 d=0d = 0 代表向东,d=1d = 1 代表向南,d=2d = 2 代表向西,d=3d = 3 代表向北。

初始时,机器人的位置为 (x0,y0)(x_0, y_0),朝向为 d0d_0。保证初始时机器人所在的位置为空地。接下来机器人将要进行 kk 次操作。每一步,机器人将按照如下的模式操作:

  1. 假设机器人当前处在的位置为 (x,y)(x, y),朝向为 dd。则它的方向上的下一步的位置 (x′,y′)(x^′, y^′) 定义如下:若 d=0d = 0,则令 (x′,y′)=(x,y+1)(x^′, y^′) = (x, y + 1),若 d=1d = 1,则令 (x′,y′)=(x+1,y)(x^′, y^′) = (x + 1, y),若 d=2d = 2,则令 (x′,y′)=(x,y−1)(x^′, y^′) = (x, y - 1),若 d=3d = 3,则令 (x′,y′)=(x−1,y)(x^′, y^′) = (x - 1, y)。

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

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

输入格式

本题有多组测试数据。

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

接下来包含 TT 组数据,每组数据的格式如下:

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

第二行包含两个正整数 x0,y0x_0, y_0 和一个非负整数 d0d_0。

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

输出格式

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

样例

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

题目来源:洛谷 P11228