题目描述

机器人在 $n imes m$ 地图上从给定位置和朝向出发，执行 $k$ 步：若前方在地图内且为空地则前进一步，否则原地右转。求经过过的不同位置数量。

输入格式

第一行输入 $T$。每组数据第一行输入 $n,m,k$；第二行输入 $x_0,y_0,d_0$；接下来 $n$ 行输入地图字符串。

输出格式

对每组数据输出一行一个整数，表示经过过的位置数量。

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

3
13

数据范围与提示

• $1 \le T\le 5$，$1 \le n,m \le 10^3$，$1 \le k\le 10^6$，$0 \le d_0 \le 3$，初始位置为空地。

来源

CSP-J 2024 T2