Python光线碰撞逻辑不正确（USACO 2020年12月青铜色第三季度“陷入常规”）

Question

我试图从USACO网站上解决这个问题。问题链接：http://www.usaco.org/index.php?page=viewproblem2&cpid=1061

农夫约翰最近扩大了他的农场的规模，所以从他的奶牛的角度来看，它现在实际上是无限大的！奶牛们把农场的放牧区想象成一个由正方形“细胞”组成的无限二维网格，每个细胞都长满了美味的草（把每个细胞想象成一个无限棋盘中的正方形）。农夫约翰的N头牛（1头）≤N≤50）从不同的单元开始；有的开始朝北，有的开始朝东

每一个小时，每一头母牛

• 如果她当前牢房里的草已经被其他人吃掉，则停止 牛
• 吃掉她当前牢房中的所有草，并向前移动一个牢房 根据她面对的方向

随着时间的推移，每头母牛都会在身后留下一条贫瘠的空细胞“车辙”

如果两头母牛在同一个移动中移动到同一个草细胞上，它们将共享该细胞，并在接下来的一小时内继续朝各自的方向移动

请确定每头牛吃的草的数量。有些牛从不停下来，因此吃了无限量的草

输入格式（输入来自终端/stdin）：

输入的第一行包含N。接下来的N行中的每一行都用一个字符来描述cow的起始位置，该字符为N（朝北）或E（朝东）以及两个非负整数x和y（0）≤x≤1000000000, 0≤Y≤100000000）给出单元格的坐标。所有x坐标彼此不同，y坐标也是如此。 为了尽可能清楚地了解方向和坐标，如果奶牛在单元格（x，y）中并向北移动，那么它将在单元格（x，y+1）中结束。如果她搬到东部，她最终会被关在（x+1，y）号牢房里

输出格式（打印输出到终端/stdout）：

打印N行输出。输出中的第i行应该描述输入中第i头牛吃的草的细胞数量。如果一头牛吃了无限量的草，则为该头牛输出“无限”

样本输入：

6
E 3 5
N 5 3
E 4 6
E 10 4
N 11 2
N 8 1

样本输出：

5
3
Infinity
Infinity
2
5

评分：

• 在测试用例2-5中，所有坐标最多为100
• 在测试用例6-10中，没有额外的约束

我的逻辑是，由于模拟碰撞的速度太慢，因为字段太大，所以我们可以根据它们的x值对奶牛进行排序，迭代奶牛的所有碰撞/交叉点，并停止应该停止的碰撞/交叉点，迭代后，打印出停止奶牛的距离。如果一头牛没有停下来，打印“无限”

我的代码：

# Defining the cow class with the original order position, x, y, distance, 
# and whether or not it stopped.
class Cow:
  def __init__(self, i, x, y):
    self.i = i 
    self.x = x
    self.y = y
    self.dist = 0
    self.stopped = False

# Get input from console and split cows into east facing and north facing cows.
n = int(input().strip())
hor = []
ver = []
ans = [0] * n
for i in range(n):
  line = input().strip().split()
  if line[0] == 'E':
    hor.append(Cow(i, int(line[1]), int(line[2])))
  else:
    ver.append(Cow(i, int(line[1]), int(line[2])))
hor.sort(key = lambda c: c.x)
ver.sort(key = lambda c: c.x)

# Iterate over every possible collision. Logic problem here:
for h in hor:
  for v in ver:
    vdist = abs(h.y - v.y)
    hdist = abs(h.x - v.x)
    if h.stopped and v.stopped:
      continue
    elif h.stopped:
      if v.x >= h.x and v.x <= h.x + h.dist and v.y <= h.y:
        if vdist > hdist:
          v.dist = vdist
          v.stopped = True
    elif v.stopped:
      if v.x >= h.x and h.y <= v.y + v.dist and v.y <= h.y:
        if hdist > vdist:
          h.dist = hdist
          h.stopped = True
    else:
      if v.x >= h.x and v.y <= h.y:
        if vdist > hdist:
          v.dist = vdist
          v.stopped = True
        if hdist > vdist:
          h.dist = hdist
          h.stopped = True
        
# Combine the lists and put them back into the original order.
cows = hor + ver
cows.sort(key = lambda c: c.i)

# Print out all the cows' distances, and it a cow hasn't stopped, replace distance with Infinity.
for i in cows:
  if not i.stopped:
    i.dist = "Infinity"
  print(i.dist)

我不确定是我的代码不正确，还是我的基本逻辑不正确。如果有人能提供修复方案，我们将不胜感激

Answer 1

为了跟踪您的算法，您可以将“交叉点查找”和“奶牛停车”分为不同的部分

import sys
from collections import namedtuple

Cow = namedtuple('Cow', ['distance','facing','x','y','number'])
lines = sys.stdin.read().strip().split('\n')

cows = [Cow(0,*[int(x) if x.isnumeric() else x for x in i.split()], e)
            for e,i in enumerate(lines[1:])]

# finding intersections
# save if distances differ, sorted descending by distance
intersections = []
for cowA, cowB in [(cowA, cowB)
                    for cowB in cows if cowB.facing == 'N'
                    for cowA in cows if cowA.facing == 'E' 
                  ]:
    if cowA.x < cowB.x and cowA.y > cowB.y:
        d1, d2 = cowB.x - cowA.x, cowA.y - cowB.y
        if d1 != d2:
            intersections.append(
                sorted([Cow(d1, *cowA[1:]),Cow(d2, *cowB[1:])], reverse=True))

# sorting intersections by larger distance
# checking if a cow reached the intersection or stopped earlier
distances = [int(10E9)] * len(cows)
for i in sorted(intersections):
    if i[1].distance < distances[i[1].number] and i[0].distance < distances[i[0].number]:
        distances[i[0].number] = i[0].distance
for i in distances:
    print('Infinity' if i==int(10E9) else i)

输出

5
3
Infinity
Infinity
2
5