結果

問題 No.367 ナイトの転身
ユーザー urutom
提出日時 2016-04-29 23:10:45
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 795 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 38,860 KB
最終ジャッジ日時 2024-10-04 18:47:47
合計ジャッジ時間 4,782 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 2 -- * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
Syntax OK

ソースコード

diff # 

DIRS=[
	[[1,2],[2,1],[-1,2],[2,-1],[1,-2],[-2,1],[-1,-2],[-2,-1]],
	[[1,1],[-1,1],[1,-1],[-1,-1]]
]
h,w=gets.split.map(&:to_i)
rh=0...h
rw=0...w
board=h.times.map{gets.chomp}
sx=sy=tx=ty=0
h.times{|i|w.times{|j|
	if board[i][j]==?S
		sx=i
		sy=j
	elsif board[i][j]==?G
		tx=i
		ty=j
	end
}}

q=[]
s=[sx,sy,0]
q.push s
visited={}
visited[s]=0
t0=[tx,ty,0]
t1=[tx,ty,1]
until q.empty?||visited[t0]||visited[t1]
	state=q.shift
	x,y,piece=state
	step=visited[state]
	d=(x-tx).abs+(y-ty).abs
	DIRS[piece].each{|dx,dy|
		nx=x+dx
		ny=y+dy
		next unless rh===nx&&rw===ny
		nd=(nx-tx).abs+(ny-ty).abs
		next if nd>d+2
		np=board[nx][ny]==?R ? 1-piece : piece
		next_state=[nx,ny,np]
		next if visited[next_state]
		visited[next_state]=step+1
		q.push next_state
	}
end

puts visited[t0]||visited[t1]||-1
0