Python碰撞逻辑不正确(USACO 2020 12月青铜器Q3“陷入车辙”)

Question

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

农夫约翰最近扩大了他的农场的规模，所以从他的奶牛的角度来看，它实际上是无限大的！奶牛认为农场的放牧区域是一个无限的二维方格“细胞”，每一个都充满了美味的草(把每个细胞想象成一个无限大的棋盘中的正方形)。每头农夫约翰的N头牛(1≤N≤50)都是在不同的牢房里开始的；有些开始朝北，有些开始向东。

每小时，每头牛

如果她目前牢房里的草已经被另一头牛吃掉了，

• 就会停下来。
• 吃掉了她目前牢房里的所有草，并根据她面临的方向移动一个细胞。--

随着时间的推移，每头母牛都会在自己身后留下一堆空空如也的“车辙”。

如果两只牛在同一行动中移动到同一个草地细胞，它们共用一个细胞，并在接下来的一小时内继续沿着各自的方向移动。

请确定每头牛吃草的数量。有些牛从来没有停过，因此吃了无穷无尽的草。

输入格式(输入来自终端/ stdin):

输入的第一行包含N。下一行N行描述牛的起始位置，字符为N(向北)或E(面向东)，两个非负整数和y (0≤x≤1000000000，0≤y≤1000000000)表示单元格的坐标。所有的x坐标都是彼此不同的，y坐标也是一样的.为了尽可能清楚地了解方向和坐标，如果母牛在单元格(x，y)中并向北移动，她将进入单元格(x，y+1)。如果她搬到了东边，她就会被关进牢房(x+1，y)。

输出格式(打印输出到终端/标准输出)：

打印N行输出。输出中的第一行应该描述输入中的第一头牛所吃的相当于草的细胞数。如果一头牛吃了无穷无尽的草，那就为那头牛输出“无限”。

示例输入：

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中，不存在额外的constraints.。

我的逻辑是，由于模拟碰撞的速度太慢，因为场很大，我们可以根据母牛的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

我的错误是hor.sort(key = lambda c: c.x)，我根据第一个元素而不是第二个元素对列表进行排序。

应该是hor.sort(key = lambda c: c.y)，因为在交叉口这才是最重要的。

Answer 2

尝试这种修改后的方法，使用set添加动作并检查交叉口。

from collections import deque
import sys

class Cow:
    def __init__(self, d, x, y, amt):
        self.d = d
        self.x = x
        self.y = y
        self.amt = amt

lines = sys.stdin.read().strip().split('\n')
n = int(lines[0])

EMPTY = set()
COW = []

for line in lines[1:]:
    d, x, y = line.split()
    x, y = int(x), int(y)
    COW.append(Cow(d, x, y, 0))

S = set()
for i in range(n):
    for j in range(n):
        S.add(abs(COW[i].x - COW[j].x))
        S.add(abs(COW[i].y - COW[j].y))

S2 = set()
for k in S:
    S2.add(k -1)
    S2.add(k)
    S2.add(k + 1)
S2.add(max(S) + 1)

dq = deque(sorted(S2))   #

SCORE = [None for _ in range(n)]
t = 0

while dq:
    #nt += 1
    dt = dq.popleft() - t
    dt = max(dt, 1)
    t += dt
    VOID = []
    
    for i in range(n):
        if SCORE[i] is None:
            if (COW[i].x, COW[i].y) in EMPTY:
                SCORE[i] = COW[i].amt
                continue
            
            VOID.append((COW[i].x, COW[i].y))
            
            if COW[i].d == 'N': COW[i].y += dt
            elif COW[i].d == 'E': COW[i].x += dt
            COW[i].amt += dt
            
    for spot in VOID: EMPTY.add(spot)

for i in range(n):
    print(SCORE[i] if SCORE[i] else 'Infinity')

Answer 3

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

​

​

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