11383: [CSP-J2024] T2 - 地图探险
[Creator : ]
Time Limit : 1.000 sec Memory Limit : 512 MiB
Description
小 A 打算前往一片丛林去探险。丛林的地理环境十分复杂,为了防止迷路,他先派遣了一个机器人前去探路。
丛林的地图可以用一个 $n$ 行 $m$ 列的字符表来表示。我们将第 $i$ 行第 $j$ 列的位置的坐标记作 $(i, j)(1 \leq i \leq n, 1 \leq j \leq m)$。如果这个位置的字符为 $\tt x$,即代表这个位置上有障碍,不可通过。反之,若这个位置的字符为 $\tt.$,即代表这个位置是一片空地,可以通过。
这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 $(x, y)(1 \leq x \leq n, 1 \leq y \leq m)$ 刻画,它表示机器人处在地图上第 $x$ 行第 $y$ 列的位置。而朝向用一个 $0 \sim 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 \leq x^′ \leq n, 1 \leq y^′ \leq m$,且 $(x^′, y^′)$ 位置上是空地。如果条件成立,则机器人会向前走一步。它新的位置变为 $(x^′, y^′)$,且朝向不变。如果条件不成立,则它会执行“向右转”操作。也就是说,令 $d^′ = (d + 1) \bmod 4$(即 $d + 1$ 除以 $4$ 的余数),且它所处的位置保持不变,但朝向由 $d$ 变为 $d^′$。
小 A 想要知道,在机器人执行完 $k$ 步操作之后,地图上所有被机器人经过的位置(包括起始位置)有几个。
丛林的地图可以用一个 $n$ 行 $m$ 列的字符表来表示。我们将第 $i$ 行第 $j$ 列的位置的坐标记作 $(i, j)(1 \leq i \leq n, 1 \leq j \leq m)$。如果这个位置的字符为 $\tt x$,即代表这个位置上有障碍,不可通过。反之,若这个位置的字符为 $\tt.$,即代表这个位置是一片空地,可以通过。
这个机器人的状态由位置和朝向两部分组成。其中位置由坐标 $(x, y)(1 \leq x \leq n, 1 \leq y \leq m)$ 刻画,它表示机器人处在地图上第 $x$ 行第 $y$ 列的位置。而朝向用一个 $0 \sim 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 \leq x^′ \leq n, 1 \leq y^′ \leq m$,且 $(x^′, y^′)$ 位置上是空地。如果条件成立,则机器人会向前走一步。它新的位置变为 $(x^′, y^′)$,且朝向不变。如果条件不成立,则它会执行“向右转”操作。也就是说,令 $d^′ = (d + 1) \bmod 4$(即 $d + 1$ 除以 $4$ 的余数),且它所处的位置保持不变,但朝向由 $d$ 变为 $d^′$。
小 A 想要知道,在机器人执行完 $k$ 步操作之后,地图上所有被机器人经过的位置(包括起始位置)有几个。
Input
本题有多组测试数据。
输入的第一行包含一个正整数 $T$,表示数据组数。
接下来包含 $T$ 组数据,每组数据的格式如下:
第一行包含三个正整数 $n, m, k$。其中 $n, m$ 表示地图的行数和列数,$k$ 表示机器人执行操作的次数。
第二行包含两个正整数 $x_0, y_0$ 和一个非负整数 $d_0$。
接下来 $n$ 行,每行包含一个长度为 $m$ 的字符串。保证字符串中只包含 $\tt{x}$ 和 $\tt{.}$ 两个字符。其中,第 $x$ 行的字符串的第 $y$ 个字符代表的位置为 $(x, y)$。这个位置是 $\tt{x}$ 即代表它是障碍,否则代表它是空地。数据保证机器人初始时所在的位置为空地。
输入的第一行包含一个正整数 $T$,表示数据组数。
接下来包含 $T$ 组数据,每组数据的格式如下:
第一行包含三个正整数 $n, m, k$。其中 $n, m$ 表示地图的行数和列数,$k$ 表示机器人执行操作的次数。
第二行包含两个正整数 $x_0, y_0$ 和一个非负整数 $d_0$。
接下来 $n$ 行,每行包含一个长度为 $m$ 的字符串。保证字符串中只包含 $\tt{x}$ 和 $\tt{.}$ 两个字符。其中,第 $x$ 行的字符串的第 $y$ 个字符代表的位置为 $(x, y)$。这个位置是 $\tt{x}$ 即代表它是障碍,否则代表它是空地。数据保证机器人初始时所在的位置为空地。
Output
对于每组数据:输出一行包含一个正整数,表示地图上所有被机器人经过的位置(包括起始位置)的个数。
Constraints
对于所有测试数据,保证:$1 \leq T \leq 5, 1 \leq n, m \leq 10^3$,$1 \leq k \leq 10^6$,$1 \leq x_0 \leq n$,$1 \leq y_0 \leq m$,$0 \leq d_0 \leq 3$,且机器人的起始位置为空地。
Sample 1 Input
2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....
Sample 1 Output
3
13
该样例包含两组数据。对第一组数据,机器人的状态以如下方式变化:
1. 初始时,机器人位于位置 $(1, 1)$,方向朝西(用数字 $2$ 代表)。
2. 第一步,机器人发现它下一步的位置 $(1, 0)$ 不在地图内,因此,它会执行“向右转”操作。此时,它的位置仍然为 $(1, 1)$,但方向朝北(用数字 $3$ 代表)。
3. 第二步,机器人发现它下一步的位置 $(0, 1)$ 不在地图内,因此,它仍然会执行“向右转”操作。此时,它的位置仍然为 $(1, 1)$,但方向朝东(用数字 $0$ 代表)。
4. 第三步,机器人发现它下一步的位置 $(1, 2)$ 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 $(1, 2)$,方向仍然朝东。
5. 第四步,机器人发现它下一步的位置 $(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)$,向右转,向右转。
1. 初始时,机器人位于位置 $(1, 1)$,方向朝西(用数字 $2$ 代表)。
2. 第一步,机器人发现它下一步的位置 $(1, 0)$ 不在地图内,因此,它会执行“向右转”操作。此时,它的位置仍然为 $(1, 1)$,但方向朝北(用数字 $3$ 代表)。
3. 第二步,机器人发现它下一步的位置 $(0, 1)$ 不在地图内,因此,它仍然会执行“向右转”操作。此时,它的位置仍然为 $(1, 1)$,但方向朝东(用数字 $0$ 代表)。
4. 第三步,机器人发现它下一步的位置 $(1, 2)$ 在地图内,且为空地。因此,它会向东走一步。此时,它的位置变为 $(1, 2)$,方向仍然朝东。
5. 第四步,机器人发现它下一步的位置 $(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)$,向右转,向右转。