1963. 光线追踪

时间限制 1000 ms   内存限制 256 MB

蔡蔡和芳芳发现了一个奇怪的房间。

这个房间可以看成由 $1\times 1$ 的方块构成的 $n$ 行 $m$ 列矩阵,某些位置上摆放着一个正偏 $45^\circ$ 或反偏 $45^\circ$ 的平面镜。同时,从房间的某处水平或竖直射入一束激光,激光在房间内穿行、反射,最终可能从房间的边缘离开,或是在房间内无限循环。

具体来说:

  • 对于向下的光线↓,"/"型的平面镜使其向左,"\"型的平面镜使其向右;
  • 对于向上的光线↑,"/"型的平面镜使其向右,"\"型的平面镜使其向左;
  • 对于向右的光线→,"/"型的平面镜使其向上,"\"型的平面镜使其向下;
  • 对于向左的光线←,"/"型的平面镜使其向下,"\"型的平面镜使其向上。

现在已知光线从第 $x$ 行第 $y$ 列正中以方向 $d$ (含义见输入数据)射入,还有房间内镜子的摆放情况,蔡蔡和芳芳想考考聪明的你,光线要走多远才会离开房间?

输入数据

第一行为5个整数 $n,m,x,y,d\ (1\le n,m\le500,1\le x \le n, 1 \le y \le m)$ 分别代表房间的长,宽,以及光线射入位置的行号,列号和方向 ,$d$ 为 $0,1,2,3$ 分别代表向上、向右,向下,向左。
接下来$n$行,每行一个长度为$m$的字符串,其中:

  • 一个英文句点"."(不含引号)代表一个空地。
  • 一个"/"代表一个正偏45°的平面镜。
  • 一个"\"代表一个反偏45°的平面镜。

保证光线射入位置是空地。

输出数据

如果光线能离开房间,输出一行一个整数,代表光线走过的路程。
否则,输出Forever!

样例输入

复制
5 5 5 1 0
../.\
.....
/.../
.....
..../ · · · · \n
     \n
     \n
     \n
     \n
     \n

样例输出

复制
15  \n

样例说明

光线依次经过的格子为(5,1),(4,1),(3,1),(3,2),(3,3),(3,4),(3,5),(2,5),(1,5),(1,4),(1,3),(2,3),(3,3),(4,3),(5,3),共15格。

提交

请先 登录

© 2024 FAQs Contact About