#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