結果
問題 |
No.2897 2集合間距離
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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))