NAQ 2018问题D

Question

成功地尝试了ICPC北美资格赛2018年问题D的“弗罗基”。任何关于代码优化和性能增强的建议和所有专题评论都是非常感谢的！

问题摘要

你正在重现经典的“青蛙”电子游戏。每一层都由一条多车道的道路组成，汽车双向行驶。每条车道内的汽车都是匀称的，以相同的速度和方向行驶。车道方向交替，上车道向左向右移动。“弗罗吉”从最下面的车道开始，她从下到下穿过马路。在每一时间步骤中，弗罗吉在四个方向之一跳下一个空间:上、下、左或右。这场比赛的目标是让弗罗吉穿过马路，越过最高车道，而不会被汽车撞到。目标给出了道路，汽车的位置和速度，以及弗罗吉的开始位置和移动，决定了她的结果后的模拟。有两种可能的结果:安全地离开最高车道或被压扁。为了更好地计划她的旅行，弗罗吉可能会在进入马路前左右移动。一旦弗罗吉进入了这条路，她只能从道路的顶端离开。也就是说，弗罗吉的道路从来不离开左，右，或下车道的边界。输入每个输入描述一个模拟。输入的第一行包含两个由空格分隔的整数：L和W。车道数由L (1≤L≤10)确定，而W (3≤W≤20)定义网格的宽度(以单元格数为单位)。后面跟着L行，每一行描述一条车道的汽车配置(从上到下)。每一行包含三个整数：O，第一辆汽车的起始偏移量；I，汽车之间的间隔；S，汽车的速度。边界是0≤O<I≤W和0≤S≤W。所有偏移量都应根据车道运动方向进行计算。最后一行输入以单个整数P (0≤P≤W−1)开头，后面是空格，然后是集合\{U,D,L,R\}中的M字符(1≤M≤L⋅W)字符串。P定义了从左侧开始的Froggie的起始位置。字符字符串定义了弗罗吉在模拟过程中的移动顺序(上、下、左、右)。输出如果弗罗吉成功地横过马路(从上车道离开道路)，输出“安全”。如果弗罗吉被车撞了，或者没有停在马路上，输出“压扁”。

froggie.py

l, w = map(int, input().split())
cars = []
for i in range(l):
  cars.append(list(map(int, input().split())))
  if i % 2 != 0:
    cars[-1][0] = w - cars[-1][0] - 1
pos, moves = input().split()
pos = (l, int(pos))

dirs = { 'U': (-1, 0), 'D': (1, 0), 'L': (0, -1), 'R': (0, 1) }
for i, c in enumerate(moves):
  pos = list(map(sum, zip(pos, dirs[c])))
  row = pos[0]
  if row == -1:
    print('safe')
    exit(0)
  elif row >= l:
    continue
  car = cars[row]
  diff = car[0] + car[2] * (i + 1) if row % 2 == 0 else car[0] - car[2] * (i + 1)
  if (diff - pos[1]) % car[1] == 0:
    print('squish')
    exit(0)
print('squish')

Answer 1

文章中的代码不能解决这个问题。考虑以下投入：

1 6
0 3 3
1 UU

邮编中的代码打印“安全”，但实际上青蛙是压扁的，因为汽车有速度3和间隔3，这意味着一辆车在每一时间步穿过车道上的每一个广场，因此车道是无法通行的。