結果

問題 No.3 ビットすごろく
ユーザー TakashinaInHub
提出日時 2016-01-30 13:37:27
言語 Ruby
(3.4.1)
結果
TLE  
実行時間 -
コード長 1,423 bytes
コンパイル時間 62 ms
コンパイル使用メモリ 7,552 KB
実行使用メモリ 38,048 KB
最終ジャッジ日時 2024-09-21 19:10:14
合計ジャッジ時間 6,893 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 4 TLE * 1 -- * 28
権限があれば一括ダウンロードができます
コンパイルメッセージ
Main.rb:65: warning: ambiguous first argument; put parentheses or a space even after `-' operator
Main.rb:75: warning: ambiguous first argument; put parentheses or a space even after `-' operator
Syntax OK

ソースコード

diff # 

def steps(n)
    i = 0
    while n > 0
        i += 1 if n%2 == 1
        n >>=  1
    end
    i
end

def mapping(n, p)
    dis = steps(p)
    fowdis = p + dis
    backdis = p - dis
    map = Array.new(2, -1)
    map[0] = fowdis if fowdis <= n
    map[1] = backdis if 1 <= backdis
    map
end

def scanroot(map_list, n, goal, fp=Array.new())
    puts "0: Start #{n}" if false
    if fp.include?(n) or n == -1
        fp << -1
        puts "1: #{fp}" if false
        return fp
    elsif n == goal
        fp << n
        puts "2: #{fp}" if false
        return fp
    end

    fp << n
    2.times { |i|
        tfp = scanroot(map_list, map_list[n-1][i], goal, Marshal.load(Marshal.dump(fp)))
        if tfp[-1] == -1
            puts "4: #{fp}" if false
            next
        end
        if tfp[-1] == goal and (fp[-1] != goal or fp.length >= tfp.length)
            puts "5: #{fp}" if false
            fp = tfp
            puts "6: #{fp}" if false
        end
    }
    
    if fp[-1] != goal
        fp << -1
        puts "7: #{fp}" if false
    end
    return fp
end

n = gets.to_i
map_list = Array.new(n)
n.times { |i|
  map_list[i] = mapping(n, i+1)
}

includeN = false
map_list.each { |d|
	2.times {|i| includeN = true if d[i] == n }
}

if includeN == false
	puts -1
	exit
end

footprint = Array.new(n, -1)
footprint = scanroot(map_list, 1, n)

if footprint[-1] == n
    puts footprint.length
else
    puts -1
end
0