时间戳

首页 > 解决方案 > Python Ray Collisions 逻辑不正确（USACO 2020 年 12 月青铜 Q3 “陷入困境”）

python - Python Ray Collisions 逻辑不正确（USACO 2020 年 12 月青铜 Q3 “陷入困境”）

问题描述

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

Farmer John 最近扩大了他的农场的规模，所以从他的奶牛的角度来看，它现在实际上是无限大的！奶牛将农场的放牧区视为由方形“单元”组成的无限 2D 网格，每个单元都种满了美味的草（将每个单元视为无限棋盘中的一个正方形）。Farmer John 的 N 头奶牛 (1≤N≤50) 中的每一头都从不同的牢房开始；有些开始朝北，有些开始朝东。

每小时，每头牛

因此，随着时间的推移，每头奶牛都会在她身后留下一个空荡荡的“车辙”。

如果两只奶牛在同一个动作中移动到同一个草地牢房，它们共享牢房并在接下来的一个小时内继续朝各自的方向移动。

请确定每头牛吃的草量。有些奶牛永远不会停下来，因此会吃掉无限量的草。

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

输入的第一行包含 N。接下来的 N 行中的每一行都描述了奶牛的起始位置，用一个字符 N（表示朝北）或 E（表示朝东）和两个非负整数 x和 y (0≤x≤1000000000, 0≤y≤1000000000) 给出一个单元格的坐标。所有 x 坐标彼此不同，y 坐标也是如此。为了尽可能清楚地了解方向和坐标，如果一头奶牛在单元格 (x,y) 中并向北移动，她最终会在单元格 (x,y+1) 中。如果她改为向东移动，她将最终进入单元格 (x+1,y)。

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

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

样品输入：

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

评分：

我的逻辑是，由于场很大，模拟碰撞会太慢，我们可以按 x 值对奶牛进行排序，遍历奶牛的所有碰撞/交叉点并停止应该停止的碰撞，在迭代之后，打印出停止的奶牛的距离。如果奶牛没有停下来，打印“Infinity”。

我的代码：

# 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)

我不确定是否只是我的代码不正确，或者这是我的基本逻辑。如果有人可以提供修复，将不胜感激。

标签： pythonarrayslistalgorithmlogic

解决方案

尝试这种修改后的方法，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')

推荐阅读