結果

問題 No.367 ナイトの転身
ユーザー urutomurutom
提出日時 2016-04-29 23:10:45
言語 Ruby
(3.3.0)
結果
TLE  
実行時間 -
コード長 795 bytes
コンパイル時間 90 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 38,860 KB
最終ジャッジ日時 2024-10-04 18:47:47
合計ジャッジ時間 4,782 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 79 ms
18,980 KB
testcase_01 AC 74 ms
12,288 KB
testcase_02 AC 75 ms
12,288 KB
testcase_03 AC 74 ms
12,160 KB
testcase_04 AC 73 ms
12,160 KB
testcase_05 AC 73 ms
12,288 KB
testcase_06 AC 73 ms
12,160 KB
testcase_07 AC 72 ms
12,416 KB
testcase_08 AC 72 ms
12,160 KB
testcase_09 AC 72 ms
12,416 KB
testcase_10 TLE -
testcase_11 TLE -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
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