Mowing the Field

题目描述

农夫 John 在管理农场的各个方面都相当可靠，除了一个方面： 他在及时且有条理地修剪草坪这件事上非常糟糕。 农场是一个由单位正方形格子组成的巨大二维网格。FJ 在时间 $t = 0$ 时从其中一个格子开始，在该格子里修剪草坪，使得它最初是唯一一块被修剪过的格子。FJ 接下来的修剪路线由一个包含 $N$ 条语句的序列描述。例如，如果第一条语句是 "W 10"，那么在时间 $t = 1$ 到 $t = 10$（即接下来的 10 个时间单位）内，FJ 每个时间单位向西移动一格，并沿途修剪草坪。完成这一串移动后，他会在时间 $t = 10$ 到达起点以西 10 格的位置，并且沿途经过的每个格子的草都已被修剪。 FJ 的进度非常缓慢，以至于他修剪过的某些草可能会在他完成全部修剪之前重新长出来。任何在时间 $t$ 被修剪过的一段草，会在时间 $t + x$ 重新出现。 FJ 的修剪路线可能会让他多次回到同一个格子，但他表示他从未遇到过一个草仍然是被修剪状态的格子。也就是说，每当他访问一个格子时，他上一次访问同一格子的时间必须至少比当前早 $x$ 个时间单位，这样草才有足够时间重新长出来。 请你确定满足 FJ 的观察始终成立时，$x$ 可能的最大值。

输入格式

第一行输入包含 $N$（$1 \leq N \leq 100$）。接下来的 $N$ 行每行包含一条语句，格式为 "D S"，其中 D 是表示方向的字符（N=北，E=东，S=南，W=西），S 是在该方向上行走的步数（$1 \leq S \leq 10$）。

输出格式

请输出使得 FJ 从不踏入草仍被修剪的格子时，$x$ 的最大值。如果 FJ 从未访问任何格子超过一次，请输出 -1。

6
N 10
E 2
S 3
W 4
S 5
E 8

10

提示

在该示例中，FJ 在时间 17 踩到一个他在时间 7 曾踩过的格子；因此，$x$ 至多为 10，否则第一次访问时修剪的草还没有重新长出来。他还在时间 26 踩到一个他在时间 2 也访问过的格子；因此 $x$ 也必须至多为 24。由于这两个限制中第一个更紧，我们可知 $x$ 至多为 10。 题目来源：Brian Dean

标签: USACO|2016|Bronze

来源

USACO|2016|Bronze