配点 : 100 点
問題文
牛君和兔君 H \times W 被困在了方格迷宫里。
暂且,想根据不知何时放进口袋的地图会合。
根据地图,迷宫似乎是由以下6种方格组成的。
# 墙壁 不能通行
. 地板 可以向相邻的上下左右方向移动(不一定必须移动)
> 可移动地板(右) 只能向右移动(一定会尝试移动)
< 可移动地板(左) 只能向左移动(一定会尝试移动)
^ 可移动地板(上) 只能向上移动(一定会尝试移动)
v 可移动地板(下) 只能向下移动(一定会尝试移动)
如果尝试向有墙的方向移动,则无法移动,停留在原来的格子。
牛君和兎君的初始位置候选有 Q 个,对于每个初始位置,求两人汇合所需的最少移动次数。
每次移动时,牛君和兎君可以独立行动。此外,由于牛君和兎君心灵相通,可以采取对彼此最优的行动。
制約
- 3 \leq H, W \leq 30
- 1 \leq Q \leq 10^5
- S_i (1 \leq i \leq H) 是上述的 6 仅由某种字符组成的长度 W 字符串。 字符
- 2 \leq SX_i, GX_i \leq W - 1 (1 \leq i \leq Q)
- 2 \leq SY_i, GY_i \leq H - 1 (1 \leq i \leq Q)
- 在给定的输入中,迷宫的外侧 1 格子被保证用墙围住。
- 在给定的输入中,乌牛君和乌库君的初始位置不会有墙。
入力
输入是按以下格式从标准输入给出的。
H W Q S_1 S_2 : S_H SX_1 SY_1 GX_1 GY_1 SX_2 SY_2 GX_2 GY_2 : SX_Q SY_Q GX_Q GY_Q
出力
输出是 由 Q 行组成。 i 线 i 输出第 n 个查询的答案。如果无法合流,则输出 -1 代替。
入力例 1
5 4 3 #### #..# #.## ##.# #### 2 2 2 2 2 3 3 2 2 2 3 4
出力例 1
0 1 -1
一开始就可能在同一个格子上。 也可能没有任何移动地板。
入力例 2
5 5 2 ##### #<..# ###^# #...# ##### 4 2 2 4 2 2 2 4
出力例 2
3 6
入力例 3
10 13 10 ############# #vvv>vvv#v<.# #.^.^<#>.v<.# #.#>v<<<>>v.# #^v<.v^v>#<<# #^.>vv^.^.^^# #<><vv>^vv^># ##<.>^>v.^<<# #.v.^v.>><v^# ############# 10 4 8 6 11 7 11 5 8 9 7 8 12 4 5 6 5 6 8 6 12 3 11 7 2 5 8 9 10 4 6 8 4 3 4 3 7 7 3 6
出力例 3
-1 2 3 -1 10 3 -1 -1 0 9