結果
問題 | No.424 立体迷路 |
ユーザー |
|
提出日時 | 2016-09-23 00:54:46 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 92 ms / 2,000 ms |
コード長 | 1,234 bytes |
コンパイル時間 | 35 ms |
コンパイル使用メモリ | 7,552 KB |
実行使用メモリ | 13,184 KB |
最終ジャッジ日時 | 2024-07-05 07:07:34 |
合計ジャッジ時間 | 3,159 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 |
コンパイルメッセージ
Syntax OK
ソースコード
H, W = gets.split.map(&:to_i)sh, sw, gh, gw = gets.split.map{|x|x.to_i - 1}@b = Array.new(H)@memo = Array.new(H)@memo2 = Array.new(H)H.times{|i|@b[i] = gets.chomp.split('').map(&:to_i)@memo[i] = Array.new(W)@memo2[i] = Array.new(W, false)}@memo[gh][gw] = true@dw = [0, 0, 1, -1]@dh = [1, -1, 0, 0]def isInside w, hreturn w >= 0 && w < W && h >= 0 && h < Henddef dfs noww, nowhif @memo[nowh][noww] != nilreturn @memo[nowh][noww]end@memo2[nowh][noww] = true4.times{|i|w1 = @dw[i] + nowww2 = 2 * @dw[i] + nowwh1 = @dh[i] + nowhh2 = 2 * @dh[i] + nowhif isInside(w1, h1) && !@memo2[h1][w1] && (@b[nowh][noww] - @b[h1][w1]).abs <= 1if dfs(w1, h1)@memo[nowh][noww] = truereturn trueendendif isInside(w2, h2) && !@memo2[h2][w2]if @b[nowh][noww] == @b[h2][w2] && @b[nowh][noww] > @b[h1][w1]if dfs(w2, h2)@memo[nowh][noww] = truereturn trueendendend}@memo[nowh][noww] = falsereturn falseendputs dfs(sw, sh) ? "YES" : "NO"