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

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

2条回答

网友

1楼 · 编辑于 2024-09-30 05:29:21

尝试这种改进的方法，使用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')

网友

2楼 · 编辑于 2024-09-30 05:29:21

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

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

相关问题更多 >

编程相关推荐

热门问题

热门文章