#4115. [USACO16JAN]Mowing the Field B

[USACO16JAN]Mowing the Field B

问题描述

农夫约翰的农场是一个大型二维网格。他从t=0时刻开始割草,初始时只有起点位置的草被割过。约翰按照N条指令移动割草:

  • 每条指令格式为"方向 步数"(方向:N北/E东/S南/W西)
  • 执行指令时,每一步移动一个单元格并在t+1时刻割草

被割过的草会在t+x时刻重新长出。约翰观察到,他每次割草时,该位置的草必定已经重新长出(即距离上次割草至少x个时间单位)。

请计算满足这一观察结果的最大x值。如果约翰从未重复访问任何单元格,输出-1。

输入格式

输入文件mowing.in:

  • 第一行:N(1≤N≤100)
  • 随后N行:每行一条指令(方向字符+步数,1≤步数≤10)

输出格式

输出文件mowing.out:

  • 最大x值(或-1)

输入样例

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

输出样例

10

样例解释

关键时间点:

  • 时间7和17访问同一单元格 → x≤10
  • 时间2和26访问同一单元格 → x≤24 因此最大x值为10