結果

問題 No.367 ナイトの転身
コンテスト
ユーザー urutom
提出日時 2016-04-29 22:52:18
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 724 bytes
コンパイル時間 88 ms
コンパイル使用メモリ 7,296 KB
実行使用メモリ 37,924 KB
最終ジャッジ日時 2024-10-04 18:31:40
合計ジャッジ時間 4,429 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10 TLE * 1 -- * 16
権限があれば一括ダウンロードができます
コンパイルメッセージ
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
t1=[tx,ty,0]
t2=[tx,ty,1]
until q.empty?||visited[t1]||visited[t2]
	state=q.shift
	x,y,piece=state
	step=visited[state]
	DIRS[piece].each{|dx,dy|
		nx=x+dx
		ny=y+dy
		next unless rh===nx&&rw===ny
		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[t1]||visited[t2]||-1
0