🧭 [CSP-J 2024] 地图探险

📖 题目描述

小 A 打算前往一片丛林去探险。丛林地形复杂，他派遣了一个机器人去探路。

丛林地图为一个 $n$ 行 $m$ 列的字符表，坐标记为 $(i, j)$（$1 \leq i \leq n, 1 \leq j \leq m$）：

• x：障碍，不可通过
• .：空地，可以通过

机器人的状态由 * *位置 $(x, y)$ * *和 * *朝向 $d$ * *两部分组成：

• $d = 0$：向东（→）
• $d = 1$：向南（↓）
• $d = 2$：向西（←）
• $d = 3$：向北（↑）

初始时，机器人位于空地 $(x_0, y_0)$，朝向 $d_0$，随后执行 $k$ 次操作。

---

🔄 操作规则

每次操作如下：

1. 根据当前朝向 $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′)$ 在地图内，且是空地：机器人向前走，位置变为 $(x′, y′)$，方向不变；
• 否则：原地右转，方向变为 $(d + 1) \bmod 4$。

---

✅ 任务目标

输出机器人最终​ * *经过的所有位置数量（包含起点） * *​。

---

📥 输入格式

第一行一个整数 $T$，表示数据组数。

接下来 $T$ 组数据，每组格式如下：

• 第 1 行：三个整数 $n, m, k$
• 第 2 行：两个整数 $x_0, y_0$ 和一个整数 $d_0$
• 第 3~$n + 2$ 行：每行一个长度为 $m$ 的字符串，组成地图

---

📤 输出格式

共 $T$ 行，每行一个整数，表示机器人经过的格子数（包含起点）。

---

🧪 输入输出样例

输入

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, 2)$
• 第四步：再向东移动到 $(1, 3)$
• 共访问 $(1, 1), (1, 2), (1, 3)$，共 3 格

---

🧭 数据范围与限制

• $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$
• 初始位置保证为空地

---

📊 测试点说明

测试点	$n$	$m$	$k$	特殊性质
1~2	1	≤2	1	无
3~4	≤100
5	1	≤1000	≤2000	全为.
6				任意
7	≤1000		≤10⁶	全为.
8~10				任意

---