結果

問題 No.424 立体迷路
ユーザー finefine
提出日時 2016-09-23 00:54:46
言語 Ruby
(3.3.0)
結果
AC  
実行時間 94 ms / 2,000 ms
コード長 1,234 bytes
コンパイル時間 206 ms
コンパイル使用メモリ 11,328 KB
実行使用メモリ 18,236 KB
最終ジャッジ日時 2023-09-18 16:52:34
合計ジャッジ時間 3,539 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 91 ms
15,192 KB
testcase_01 AC 86 ms
15,296 KB
testcase_02 AC 85 ms
15,192 KB
testcase_03 AC 86 ms
15,192 KB
testcase_04 AC 85 ms
15,112 KB
testcase_05 AC 86 ms
15,056 KB
testcase_06 AC 85 ms
15,028 KB
testcase_07 AC 85 ms
15,320 KB
testcase_08 AC 86 ms
15,364 KB
testcase_09 AC 86 ms
15,100 KB
testcase_10 AC 84 ms
15,360 KB
testcase_11 AC 85 ms
15,328 KB
testcase_12 AC 83 ms
15,264 KB
testcase_13 AC 85 ms
15,168 KB
testcase_14 AC 88 ms
15,116 KB
testcase_15 AC 86 ms
15,160 KB
testcase_16 AC 86 ms
15,052 KB
testcase_17 AC 87 ms
15,412 KB
testcase_18 AC 87 ms
15,292 KB
testcase_19 AC 88 ms
15,492 KB
testcase_20 AC 86 ms
15,200 KB
testcase_21 AC 84 ms
15,280 KB
testcase_22 AC 83 ms
15,036 KB
testcase_23 AC 83 ms
15,152 KB
testcase_24 AC 91 ms
18,168 KB
testcase_25 AC 94 ms
18,236 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