分数: 1200 点
问题陈述
在 AtCoder 共和国的首都高羽市,有 N 道路向东和向西延伸,以及 M 道路南北延伸。没有其他道路。 的 i-从北到西的第一条东西路 j西十字路口第-南北向路口 (i, j)。 东西走向的两条路不相交,南北走向的两条路也不相交。 同一方向相邻两条道路之间的距离为 1.
每条路都是单向的;一个人只能朝一个方向行走。每条道路的允许方向由字符串描述 S 长度 N 和一个字符串 T 长度 M,如下:
- 如果 i- 第一个字符 S is
W,只能沿着这条路向西走 i- 从北起的东西向道路; - 如果 i- 第一个字符 S is
E,只能沿着这条路向东走 i- 从北起的东西向道路; - 如果 i- 第一个字符 T is
N,只能沿着这条路向北走 i西起第-条南北向路; - 如果 i- 第一个字符 T is
S,只能沿着这条路向南走 i从西数第 3 条西南路。
处理以下内容 Q 查询:
- 在 i第一个查询, 给出了 a_i, b_i, c_i 和 d_i 。到达交叉路口的最短距离是多少 (c_i, d_i) 从十字路口 (a_i, b_i) 沿着马路步行?
约束
- 2 \leq N \leq 100000
- 2 \leq M \leq 100000
- 2 \leq Q \leq 200000
- |S| = N
- S 包括
W和E. - |T| = M
- T 包括
N和S. - 1 \leq a_i \leq N
- 1 \leq b_i \leq M
- 1 \leq c_i \leq N
- 1 \leq d_i \leq M
- (a_i, b_i) \neq (c_i, d_i)
输入
输入由标准输入按以下格式给出:
N M Q S T a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 : a_Q b_Q c_Q d_Q
输出
在 i第行,打印对 i第一个查询。如果交叉路口 (c_i, d_i) 无法从路口到达 (a_i, b_i) 沿着道路行走,打印 -1 代替。
样本输入 1
4 5 4 EEWW NSNNS 4 1 1 4 1 3 1 2 4 2 3 2 3 3 3 5
示例输出 1
6 11 5 4
各路允许行驶方向如下图所示(北向上):

对于四个查询中的每一个,实现最小行驶距离的路线如下:

示例输入 2
3 3 2 EEE SSS 1 1 3 3 3 3 1 1
示例输出 2
4 -1
旅行可能无法进行。
示例输入 3
9 7 10 EEEEEWEWW NSSSNSN 4 6 9 2 3 7 6 7 7 5 3 5 1 1 8 1 4 3 5 4 7 4 6 4 2 5 8 6 6 6 2 7 2 4 7 5 7 2 9 7
示例输出 3
9 -1 4 9 2 3 7 7 6 -1