2024 T2 地图探险

主知识点：模拟与字符串。交叉标签：模拟、网格。
暴力标注：不属于重点 DP 退路题。
OJ 使用标准输入与标准输出。原比赛文件名为 explore.in / explore.out；下方如保留原文件约定，以本句的 OJ 约定为准。
时限 1 秒；内存 512 MiB；测试点 10；总分 100。
数据来源：公开存档数据；未逐文件对照官网下载包。

题目描述

地图为 $n$ 行 $m$ 列，. 是可通行空地，x 是障碍。机器人从给定空地 $(x_0,y_0)$ 出发，方向 0、1、2、3 分别表示东、南、西、北。

执行 $k$ 步操作：若正前方在地图内且为空地，则前进一格；否则原地右转，方向变为 $(d+1)\bmod4$。转向也消耗一步。求执行后经过的不同格子数，包含起始格子。

输入格式

本题有多组测试数据。

输入的第一行包含一个正整数 $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}$ 即代表它是障碍，否则代表它是空地。数据保证机器人初始时所在的位置为空地。

输出格式

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

样例

样例 1

输入：

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

输出：

3
13

数据范围与特殊性质

对于所有测试数据，保证：$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$	$=1$	$\leq 2$	$=1$	无
$2$
$3$	$\leq 10^2$
$4$
$5$	$=1$	$\leq 10^3$	$\leq 2\times 10^3$	地图上所有位置均为空地
$6$				无
$7$	$\leq 10^3$		$\leq 10^6$	地图上所有位置均为空地
$8$				无
$9$
$10$

附加样例

本题的公开样例整理在对应的“样例”ZIP 中。样例不计入评测测试点；题面中的样例也已保留。

来源与整理说明

题目原作者/发布者：中国计算机学会 CCF / NOI。题意经过改写，保留公式、输入输出、样例及约束；知识点和暴力标注为本次整理补充。

• 题面及约束校对来源：洛谷 CCF_NOI 题目 P11228
• 赛事：CSP-J 第二轮入门级 2024。
• 详细数据来源、版本和哈希见总包 来源与校验/manifest.json。