結果

問題 No.424 立体迷路
コンテスト
ユーザー horiesiniti
提出日時 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

ソースコード

diff # 

def f(x,y,h,w)
	return false if x<0 || x>=h || y<0 || y>=w
	return true
end

h,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]]=0
dp={}
dp[[sx,sy]]=0
while true
	dp2={}
	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)==false
				next
			end
			d=(m[x2][y2]-m[x1][y1]).abs
			add=0
			if d>1
				next
			elsif d==1
				add=1
			end
			e3=[x2,y2]
			k=hs[e]+add
			if hs.key?(e3)==false || hs[e3]>k
				hs[e3]=k
				dp2[e3]=k
			end
		}
		4.times{|i|
			x2=x1+dx2[i]
			y2=y1+dy2[i]
			x3=x1+dx2[i]/2
			y3=y1+dy2[i]/2
			if f(x2,y2,h,w)==false
				next
			end
			d=(m[x2][y2]-m[x1][y1]).abs
			if d!=0
				next
			end
			if m[x3][y3]>=m[x1][y1]
				next
			end
			e3=[x2,y2]
			k=hs[e]+1
			if hs.key?(e3)==false || hs[e3]>k
				hs[e3]=k
				dp2[e3]=k
			end
		}
	}
	break if dp.empty? ==true
	break if dp.key?([gx,gy]) ==true
	dp=dp2
end
if dp.key?([gx,gy])==true
	puts "YES"
else
	puts "NO"
end
0