1232: 谢博博的一天
题目描述
题目背景：
谢博博是一种很可爱的动物……
谢博博很喜欢一个人在铁一机房里乱转……
谢博博是一种很不聪明的动物……
谢博博会撞到墙上之后转弯……
谢博博是一种很喜欢右边的动物……
谢博博撞墙之后只会右转……
谢博博是一种喜欢慢慢走路的动物……
谢博博一次只会走一格……
谢博博是一个有计划的动物……
谢博博想让你帮他算出来他在机房一天可以到的地方……
谢博博是一种喜欢幻想的动物……
谢博博想要 $AK$ $IOI$ （雾
题目描述
机房一个 $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)$ 刻画，它表示谢博博 行第 $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 <= x′ <= n, 1 <= y′ <= m$，且 $(x′, y′)$ 位置上是空地。如果条件成立，则谢博博会向前走一步。它新的位置变为 $(x′, y′)$，且朝向不变。如果条件不成立，则它会执行“向右转”操作。也就是说，令 $d′ = (d + 1) mod 4$（即 $d + 1$ 除以 $4$ 的余数），且它所处的位置保持不变，但朝向由 $d$ 变为 $d′$。
输入
输出
样例输入 复制
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^{18}$，$1 \leq x_0 \leq n$，$1 \leq y_0 \leq m$，$0 \leq d_0 \leq 3$，且谢博博的起始位置为空地。
（学长提示：为了你们不要 $听取TLE声一片$，有50%的 $k \leq 10^5$）
（填空题：不开_________见____）
彩蛋：https://www.luogu.com.cn/user/1046406