解题思路

把“蛋仔静止的位置”看成图上的一个点。 每次从某个静止点出发，任选一个方向开始滚动，直到再次停下，这整个过程都只算 1 次滚动，因此这是一个典型的最短路分层问题，直接用 BFS 求最少滚动次数。

难点在于如何正确模拟“一次滚动”：

1. 蛋仔遇到障碍物 # 或地图外侧虚拟障碍时会停下。
2. 蛋仔进入挡板 / 或 \ 后会立刻改变方向继续滚动，不能停在挡板上。
3. 如果某个挡板按规则反弹后的下一格是障碍物或另一个挡板，那么这个挡板不可进入，蛋仔会停在进入挡板前一格。

题目描述

给定一个$m$行$n$列的地图，蛋仔从起点$(sr,sc)$出发，需要到达终点$(er,ec)$。

蛋仔每次可以选择向上、下、左、右四个方向之一开始滚动。一旦开始滚动，在遇到阻挡前无法主动停下。为了防止蛋仔滚出地图，地图外侧视为额外包裹了一圈障碍物。

地图中有三类特殊格子：#为障碍物，蛋仔不能进入；/为斜挡板；\为反斜挡板。题目保证起点和终点所在格子均不是特殊格子，给出的特殊格子坐标互不重复。

挡板本身占据一个格子，蛋仔进入挡板格后会立即根据挡板类型改变方向并继续滚动。/型挡板：从左侧进入改为向上，从右侧进入改为向下，从上方进入改为向左，从下方进入改为向右。\型挡板：从左侧进入改为向下，从右侧进入改为向上，从上方进入改为向右，从下方进入改为向左。

补充说明:一次“滚动"定义为从某个静止位置出发，选择一个方向，直到再次停下为止，即使途中多次改变方向也只记为$1$次滚动。若蛋仔即将进入某个挡板格，但按挡板规则计算出的出口方向对应的下一格是障碍物或另一个挡板，则该挡板视为不可进入，蛋仔停在进入挡板前的那一格。只要蛋仔在某次滚动过程中经过终点格，就视为成功到达，不要求恰好停在终点。若蛋仔在挡板间无限反弹且经过了终点，仍视为可以到达。

请求出蛋仔从起点到终点的最少滚动次数，若无法到达输出$-1$。

输入描述

第一行输入两个整数 $m,n(1<m,n <100)$，表示地图的行数和列数。

第二行输入一个整数$k(0 <k< 10000)$，表示特殊格子的数量。

接下来 $k$行，每行输入三个值$r,c,ch$，表示第$r$行第$c$ 列是一个特殊格子，类型为 $ch$(#、/或\ )。

接下来一行输入两个整数 $sr,sc(1< sr ≤ m,1≤ sc ≤n)$，表示起点坐标。

最后一行输入两个整数 $er,ec(1< er < m,1< ec <n)$，表示终点坐标。所有坐标均为$1-based$。

输出描述

输出一个整数，表示蛋仔到达终点的最少滚动次数;若无法到达，输出$-1$。

样例1

输入

3 5
3
1 3 #
1 5 \
2 5 /
2 1
2 3

输出

1

说明

地图如下($s$ 为起点，$E$为终点，外圈为虚拟障碍物):

#######
#..#.\#
#S.E./#
#.....#
#######

蛋仔从起点向右滚动$1$次，滚动过程中经过终点，答案为 $1$。