Python 射线碰撞逻辑不正确（USACO 2020 年 12 月青铜 Q3 "Stuck in a Rut"）
Python Ray Collisions Logic Incorrect (USACO 2020 December Bronze Q3 "Stuck in a Rut")
我正在尝试从 USACO 网站上解决这个问题。问题 Link：http://www.usaco.org/index.php?page=viewproblem2&cpid=1061
Farmer John 最近扩大了他的农场规模，因此从他的奶牛的角度来看，现在农场实际上是无限大的！奶牛们将农场的放牧区想象成一个由方形“单元格”组成的无限二维网格，每个单元格都装满了美味的草（将每个单元格想象成无限棋盘中的一个正方形）。 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) 单元格。
输出格式（打印输出到终端/stdout）：
打印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
得分：
- 测试用例2-5，所有坐标最多为100。
- 在测试用例 6-10 中，没有附加约束。
我的逻辑是，因为模拟碰撞会太慢，因为场很大，我们可以按它们的 x 值对奶牛进行排序，遍历所有 collisions/intersections 奶牛并停止那些应该停止，并在迭代后，打印出停止的奶牛的距离。如果奶牛没有停下来，打印“无限”。
我的代码：
# 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)
我不确定是我的代码不正确，还是我的基本逻辑不正确。如果有人可以提供修复，我们将不胜感激。
试试这个修改后的方法，使用 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')
要跟踪您的算法，您可以将 'intersection-finding' 和 'cow-stopping' 分成不同的部分。
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
我的错误是 hor.sort(key = lambda c: c.x) 我按第一个元素而不是第二个元素对列表进行排序。
应该是 hor.sort(key = lambda c: c.y)，因为这在十字路口很重要。
我正在尝试从 USACO 网站上解决这个问题。问题 Link：http://www.usaco.org/index.php?page=viewproblem2&cpid=1061
Farmer John 最近扩大了他的农场规模，因此从他的奶牛的角度来看，现在农场实际上是无限大的！奶牛们将农场的放牧区想象成一个由方形“单元格”组成的无限二维网格，每个单元格都装满了美味的草（将每个单元格想象成无限棋盘中的一个正方形）。 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) 单元格。
输出格式（打印输出到终端/stdout）：
打印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
得分：
- 测试用例2-5，所有坐标最多为100。
- 在测试用例 6-10 中，没有附加约束。
我的逻辑是，因为模拟碰撞会太慢，因为场很大，我们可以按它们的 x 值对奶牛进行排序，遍历所有 collisions/intersections 奶牛并停止那些应该停止，并在迭代后，打印出停止的奶牛的距离。如果奶牛没有停下来，打印“无限”。
我的代码：
# 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)
我不确定是我的代码不正确，还是我的基本逻辑不正确。如果有人可以提供修复，我们将不胜感激。
试试这个修改后的方法，使用 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')
要跟踪您的算法，您可以将 'intersection-finding' 和 'cow-stopping' 分成不同的部分。
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
我的错误是 hor.sort(key = lambda c: c.x) 我按第一个元素而不是第二个元素对列表进行排序。
应该是 hor.sort(key = lambda c: c.y)，因为这在十字路口很重要。