結果

問題 No.424 立体迷路
ユーザー finefine
提出日時 2016-09-23 00:54:46
言語 Ruby
(3.3.0)
結果
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
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 90 ms
12,032 KB
testcase_01 AC 90 ms
12,288 KB
testcase_02 AC 84 ms
12,288 KB
testcase_03 AC 89 ms
12,160 KB
testcase_04 AC 87 ms
12,288 KB
testcase_05 AC 86 ms
12,032 KB
testcase_06 AC 85 ms
12,160 KB
testcase_07 AC 85 ms
12,160 KB
testcase_08 AC 82 ms
12,032 KB
testcase_09 AC 83 ms
12,032 KB
testcase_10 AC 81 ms
11,904 KB
testcase_11 AC 84 ms
12,032 KB
testcase_12 AC 86 ms
12,032 KB
testcase_13 AC 84 ms
12,032 KB
testcase_14 AC 85 ms
12,032 KB
testcase_15 AC 85 ms
12,032 KB
testcase_16 AC 85 ms
12,032 KB
testcase_17 AC 87 ms
12,160 KB
testcase_18 AC 88 ms
12,288 KB
testcase_19 AC 88 ms
12,288 KB
testcase_20 AC 85 ms
12,160 KB
testcase_21 AC 84 ms
12,160 KB
testcase_22 AC 83 ms
12,160 KB
testcase_23 AC 83 ms
12,032 KB
testcase_24 AC 91 ms
13,056 KB
testcase_25 AC 92 ms
13,184 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
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