AtCoder ABC 057 B – Checkpoints Python解説
Checkpoints
今回の問題はこちら「Checkpoints」。N人の学生とM個のチェックポイントが与えられるので、マンハッタン距離で最短のチェックポイントの番号を出力する問題です。
与えられる学生とチェックポイントの座標を使って、地道に解いていきます。
n, m = map(int, input().split())
x_1 = []
y_1 = []
x_2 = []
y_2 = []
for _ in range(n):
x1, y1 = map(int, input().split())
x_1.append(x1)
y_1.append(y1)
for _ in range(m):
x2, y2 = map(int, input().split())
x_2.append(x2)
y_2.append(y2)
for i in range(n):
pos = 10 ** 9
ans = 0
for j in range(m):
manhattan = abs(x_1[i] - x_2[j]) + abs(y_1[i] - y_2[j])
if pos > manhattan:
pos = manhattan
ans = j + 1
print(ans)学生の座標をx_1、y_1とおき、チェックポイントの座標をx_2、y_2とおいています。posは与えられる入力が最大10^8と大きい数字なので、それよりも大きい10^9を入れています。
ansは最短距離の番号を入れます。
manhattanで学生とチェックポイントの絶対値を取ったらposと比較し、距離が小さくなっていたらposとansを更新しています。
学生が変わるたびにposを10^9で初期化することを忘れずに行いましょう。