当前没有测试数据。

探索地阵 (explore)

题目描述

小 A 派遣一个机器人在 $n \times m$ 的丛林地图中探险。 地图为一个 $n$ 行 $m$ 列的字符表：

• x 表示障碍物，不可通过。
• . 表示空地，可以通过。

机器人由当前位置 $(x, y)$ 和朝向 $d$ 共同决定。 朝向 $d$ 使用 0~3 的整数表示：

• $d=0$：向东（即列数增加，对应右侧）
• $d=1$：向南（即行数增加，对应下方）
• $d=2$：向西（即列数减小，对应左侧）
• $d=3$：向北（即行数减小，对应上方）

机器人共进行 $k$ 次操作，每一步遵循以下逻辑：

1. 根据当前朝向 $d$，计算前方下一步的坐标 $(x', y')$。
2. 判断 $(x', y')$ 是否在地图范围内（$1 \le x' \le n$，$1 \le y' \le m$）且为空地（字符不为 x）。
3. 如果条件成立，机器人向前走一步，位置更新为 $(x', y')$，不改变朝向。
4. 如果条件不成立，机器人原地向右转（朝向 $d$ 变为 $(d+1) \pmod 4$），位置不变。

注意：无论前进还是原地右转，都消耗 1 次操作（即算作 $k$ 次操作中的 1 次）。

请计算出 $k$ 次操作结束后，机器人一共访问过多少个不同的位置（包含机器人的初始位置）。

输入格式

第一行包含一个正整数 $T$，表示测试数据组数。 对于每组数据： 第一行包含三个正整数 $n, m, k$，分别表示地图的行数、列数以及操作次数。 第二行包含三个整数 $x_0, y_0, d_0$，表示机器人的初始行坐标、初始列坐标和初始朝向。 接下来 $n$ 行，每行包含一个长度为 $m$ 的字符串，表示地图。字符串仅包含 x 和 .。保证初始位置为空地。

输出格式

输出 $T$ 行，每行一个整数，表示每组数据中机器人经过的不同位置的数量。

数据范围

• $1 \le T \le 5$
• $1 \le n, m \le 10^3$
• $1 \le k \le 10^6$
• 初始位置 $(x_0, y_0)$ 保证合法且不在障碍物上。