← 返回题目列表

AtCoder · ukuku09_c

C. 迷宫

中文机器翻译题面 查看原题

配点 : 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