結果

問題 No.424 立体迷路
ユーザー fine
提出日時 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

ソースコード

diff # 

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, h
    return w >= 0 && w < W && h >= 0 && h < H
end

def dfs noww, nowh
    if @memo[nowh][noww] != nil
        return @memo[nowh][noww]
    end
    @memo2[nowh][noww] = true
    4.times{|i|
        w1 = @dw[i] + noww
        w2 = 2 * @dw[i] + noww
        h1 = @dh[i] + nowh
        h2 = 2 * @dh[i] + nowh
        if isInside(w1, h1) && !@memo2[h1][w1] && (@b[nowh][noww] - @b[h1][w1]).abs <= 1
            if dfs(w1, h1)
                @memo[nowh][noww] = true
                return true
            end
        end
        if 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] = true
                    return true
                end
            end
        end
        }
    @memo[nowh][noww] = false
    return false
end

puts dfs(sw, sh) ? "YES" : "NO"
0