ダイクストラ法
なんか、すごいプログラマの人が出したという迷路を解く問題http://okajima.air-nifty.com/b/2010/01/post-abc6.htmlをいまさらRubyで行った。
ダイクストラ法の勉強で2時間
それをコードに落とすのに2時間
「Oh! No! 動かなーい」で3時間
結果を表示するのに1時間
制限時間の3時間を大幅に越えている。
参考にさせてもらったURL http://www.sousakuba.com/Programming/algo_root.html
穢いプログラムも一応のせておこう。Rubyって難しい・・・・
JavaScriptのつもりでテキトーに変数使ってエラい目にあった。
うんこくさいグローバル変数の前には$をつけろですよ
しかし、へたくそなrubyプログラムと言うのは縦に伸びるなあ。
#!/usr/bin/ruby $start = nil $goal = nil class Dikstr_node def initialize(x, y, cost, prev) @px = x; @py = y; @prev_node = prev; @cost_before = cost + (prev ? prev.cost_before : 0) end attr_accessor :px, :py, :prev_node, :cost_before end def parse_maze( f ) ret = []; x = y = 0 f.each do |line| line.strip! l = Array.new x = 0 line.each_byte do |b| if (b == 42) # * l.push :wall; elsif (b == 32) # :space l.push nil; elsif (b == 83) print "start1 =#{$start}\n" $start = Dikstr_node.new(x, y, 0, nil) print "start2 =#{$start}\n" l.push $start else (b == ?G) $goal = Dikstr_node.new(x, y, 100000000, nil) l.push $goal end x += 1 end y += 1; ret.push l end ret end def next_node(m, direct, cur) x = cur.px y = cur.py case direct when :up y -= 1; when :down y += 1; when :right x += 1; when :left x -= 1; end # p "m[#{y}][#{x}] = #{m[y][x]}" if (m[y][x] == nil ) m[y][x] = Dikstr_node.new(x, y, 1, cur) ; elsif (m[y][x] != :wall) if (m[y][x].cost_before > cur.cost_before + 1) m[y][x].prev_node = cur; m[y][x].cost_before = cur.cost_before + 1; else return :already end end abort("nil???") if m[y][x] == nil m[y][x] end def next_nodes_list(m, cur) l = []; directs = [:up, :down, :right, :left]; directs.each do |d| l.push next_node(m, d, cur); end l end def insert_min(a, node) i = 0 while(i < a.length) p "a[#{i}] is null length = #{a.length}" if a[i] == nil break if a[i].cost_before > node.cost_before i += 1 end a.insert(i, node); end def disp_result( m ) l = [] m.each do |line| str = "" i = 0 line.each do |x| if (x == :wall) str[i] = ?* else str[i] = 32.chr end i += 1 end l.push str end l[$goal.py][$goal.px] = ?G l[$start.py][$start.px] = ?S cur = $goal.prev_node while (cur != $start) # print "(#{cur.px} #{cur.py})" l[cur.py][cur.px] = ?$ #break if (cur == $start) #print "->" cur = cur.prev_node end #print "\n" l.each {|line| puts line} end def resolve_maze( m ) # cur = $start x_max = m[0].length - 1; y_max = m.length - 1; print "m.length = #{m.length} \n" print "m[0].length = #{m[0].length} \n" q = [] q.push $start #p m # q から一件取り出す count = 0 while(true) count += 1 cur = q.shift # 取り出したデータからnext_nodes_listを実行 if (count > 200) #p m exit end # nodeが Dikstr_nodeで、$goalじゃなかったら 入れる。 # $goalだったら終了。 # p cur abort ("cur is nil") if (cur == nil) l = next_nodes_list(m, cur); l.each do |n| # p "#{n} : #{n.class}" if (n == $goal) p "ok" disp_result m exit end abort ("n is nil") if (n == nil) if (n != :wall && n != :already && n != $goal) # p "#{n.px} : #{n.py} : #{n.cost_before}" insert_min(q, n) end end end end m = nil if ARGV[0] then File.open(ARGV[0]) do |f| m = parse_maze f end else m = parse_maze $stdin end #p m print "start =#{$start} #{$start.px} #{$start.py}\n" print "goal = #{$goal} #{$goal.px} #{$goal.py} \n" resolve_maze m
実行結果
************************** *S* *$$$$ * *$* *$ *$ ************* * *$*$$$* $ ************ * *$$$ * $$$$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$ *$$$$$$$$G * * *$$$$$$*********** * * * * ******* * * * * * **************************