結果

問題 No.2897 ２集合間距離
コンテスト
ユーザー norioc
提出日時 2025-02-12 00:13:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,664 ms / 3,500 ms
コード長 800 bytes
コンパイル時間 309 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 267,628 KB
最終ジャッジ日時 2025-02-12 00:13:41
合計ジャッジ時間 13,615 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import deque

N = int(input())
ss = []
for i in range(N):
    x, y = map(int, input().split())
    ss.append((x, y))

M = int(input())
ts = set()
for i in range(M):
    x, y = map(int, input().split())
    ts.add((x, y))


def neighbors(x, y):
    size = 10 ** 3
    for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        nx = x + dx
        ny = y + dy
        if 0 <= nx <= size and 0 <= ny <= size:
            yield nx, ny


def distance(x1, y1, x2, y2):
    return abs(x1 - x2) + abs(y1 - y2)


used = set()
q = deque([(x, y, 0) for x, y in ss])
while q:
    x, y, step = q.popleft()
    if (x, y) in ts:
        print(step)
        break

    for nx, ny in neighbors(x, y):
        if (nx, ny) in used: continue
        used.add((nx, ny))
        q.append((nx, ny, step+1))
0