結果
問題 | No.424 立体迷路 |
ユーザー |
![]() |
提出日時 | 2018-03-17 10:41:12 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 94 ms / 2,000 ms |
コード長 | 1,108 bytes |
コンパイル時間 | 112 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 12,672 KB |
最終ジャッジ日時 | 2024-07-05 07:15:22 |
合計ジャッジ時間 | 2,789 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
コンパイルメッセージ
Syntax OK
ソースコード
def f(x,y,h,w)return false if x<0 || x>=h || y<0 || y>=wreturn trueendh,w=gets.split.map{|e| e.to_i}sx,sy,gx,gy=gets.split.map{|e| e.to_i-1}m=STDIN.read.split.map{|e|e.split("").map{|e2|e2.to_i}}dx=[0,-1,0,1]dy=[1,0,-1,0]dx2=[0,-2,0,2]dy2=[2,0,-2,0]hs={}hs[[sx,sy]]=0dp={}dp[[sx,sy]]=0while truedp2={}dp.keys.each{|e|x1=e[0]y1=e[1]4.times{|i|x2=x1+dx[i]y2=y1+dy[i]if f(x2,y2,h,w)==falsenextendd=(m[x2][y2]-m[x1][y1]).absadd=0if d>1nextelsif d==1add=1ende3=[x2,y2]k=hs[e]+addif hs.key?(e3)==false || hs[e3]>khs[e3]=kdp2[e3]=kend}4.times{|i|x2=x1+dx2[i]y2=y1+dy2[i]x3=x1+dx2[i]/2y3=y1+dy2[i]/2if f(x2,y2,h,w)==falsenextendd=(m[x2][y2]-m[x1][y1]).absif d!=0nextendif m[x3][y3]>=m[x1][y1]nextende3=[x2,y2]k=hs[e]+1if hs.key?(e3)==false || hs[e3]>khs[e3]=kdp2[e3]=kend}}break if dp.empty? ==truebreak if dp.key?([gx,gy]) ==truedp=dp2endif dp.key?([gx,gy])==trueputs "YES"elseputs "NO"end