結果

問題 No.2675 KUMA
ユーザー sasa8uyauya
提出日時 2025-03-03 06:22:02
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 743 ms / 2,000 ms
コード長 605 bytes
コンパイル時間 444 ms
コンパイル使用メモリ 82,116 KB
実行使用メモリ 76,716 KB
最終ジャッジ日時 2025-03-03 06:22:12
合計ジャッジ時間 9,507 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 47
権限があれば一括ダウンロードができます

ソースコード

diff # 

n=int(input())
a=[tuple(map(int,input().split())) for i in range(n)]
p={}
for i in range(n):
  ax,ay=a[i]
  dx1,dy1=2,0
  dx2,dy2=0,1
  for j in range(4):
    bx,by=ax+dx1+dx2,ay+dy1+dy2
    b=(bx,by)
    if b not in a:
      if b not in p:
        p[b]=[0]*4
      p[b][j-2]|=1<<i
    bx,by=ax+dx1-dx2,ay+dy1-dy2
    b=(bx,by)
    if b not in a:
      if b not in p:
        p[b]=[0]*4
      p[b][j-2]|=1<<i
    dx1,dy1=-dy1,dx1
    dx2,dy2=-dy2,dx2
X=100
q=[X]*(1<<n)
q[0]=0
for b in p:
  for i in reversed(range(1<<n)):
    for m in p[b]:
      q[i|m]=min(q[i|m],q[i]+1)
print(q[-1] if q[-1]<X else -1)
0