結果
問題 | No.340 雪の足跡 |
ユーザー |
![]() |
提出日時 | 2020-09-23 02:30:49 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 455 ms / 1,000 ms |
コード長 | 990 bytes |
コンパイル時間 | 141 ms |
コンパイル使用メモリ | 82,284 KB |
実行使用メモリ | 194,452 KB |
最終ジャッジ日時 | 2024-06-27 03:43:28 |
合計ジャッジ時間 | 7,967 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 32 |
ソースコード
import sysreadline=sys.stdin.readlinew,h,n=map(int,readline().split())s1=[[0]*w for i in range(h)]s2=[[0]*h for i in range(w)]for i in range(n):m=int(readline())b=list(map(int,readline().split()))for j in range(m):x1,y1=divmod(b[j],w)x2,y2=divmod(b[j+1],w)if x1==x2:if y1>y2:y1,y2=y2,y1s1[x1][y1]+=1s1[x1][y2]-=1else:if x1>x2:x1,x2=x2,x1s2[y1][x1]+=1s2[y1][x2]-=1from itertools import accumulatefor i in range(h):s1[i]=list(accumulate(s1[i]))for i in range(w):s2[i]=list(accumulate(s2[i]))INF=9**9d=[INF]*h*wd[0]=0que=[0]for p in que:x, y=divmod(p, w)d0=d[p]p1,p2,p3,p4=(x-1)*w+y,(x+1)*w+y,x*w+y-1,x*w+y+1if x-1>=0and s2[y][x-1]and d[p1]>d0+1:d[p1]=d0+1que.append(p1)if x+1<h and s2[y][x]and d[p2]>d0+1:d[p2]=d0+1que.append(p2)if y-1>=0and s1[x][y-1]and d[p3]>d0+1:d[p3]=d0+1que.append(p3)if y+1<w and s1[x][y]and d[p4]>d0+1:d[p4]=d0+1que.append(p4)print(d[-1]if d[-1]<INF else"Odekakedekinai..")