← 返回题目列表

AtCoder · exawizards2019_f

F. 更现实的曼哈顿距离

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

分数: 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