<p>尝试这种改进的方法,使用<code>set</code>添加运动并检查交叉点</p>
<pre><code>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')
</code></pre>