#P3362. [Usaco2004 Feb]Navigation Nightmare 导航噩梦
[Usaco2004 Feb]Navigation Nightmare 导航噩梦
[USACO 2004 Feb] Navigation Nightmare 导航噩梦
题目描述
农夫约翰的村庄里有 个农场。农场编号为 到 。 条道路都是水平或竖直的;道路之间不交叉,农场只位于道路端点,每个道路端点都有一个农场。每个农场在东、西、南、北四个方向上至多各有一条相连的道路。任意两个农场之间恰好有一条简单路径。 图中的农场用 F1 到 F7 表示,括号中为道路长度。示意图不按比例绘制。
F1 --- (13) ---- F6 --- (9) ----- F3
| |
(3) |
| (7)
F4 --- (20) -------- F2 |
| |
(2) F5
|
F7
约翰丢失了农场地图,只能逐条从计算机备份中恢复道路记录。例如,农场 向北行进 个单位可以到达农场 ,农场 向东行进 个单位也可以到达农场 。
邻居鲍伯会在恢复地图的过程中询问两个农场的曼哈顿距离。点 与 的曼哈顿距离是 ;上例中农场 到 的距离为 。若已恢复的道路信息不足以确定距离,约翰回答 。
输入格式
从标准输入读入。第一行是两个整数 ,表示农场数和道路数。接下来 行,每行给出三个整数和一个字符 ,表示从农场 沿方向 行进 个单位到达农场 。 为 N(北)、E(东)、S(南)或 W(西)。
随后一行是整数 ,表示询问数。接下来 行,每行三个整数 ,询问只知道前 条道路记录时农场 与 的曼哈顿距离。
输出格式
向标准输出按询问的输入顺序输出 行。每行输出相应的距离;若无法确定,输出 。
7 6
1 6 13 E
6 3 9 E
3 5 7 S
4 1 3 N
2 4 20 W
4 7 2 S
3
1 6 1
1 4 3
2 6 6
13
-1
10
样例解释
第一问只知道第一条道路,已能确定 与 相距 。第二问时仍无法推出 与 的距离。最后一问中,农场 在农场 以北 、以西 ,故距离为 。
数据范围与约定
,,。各农场编号在 到 之间。另有 ,。