第13回オフラインリアルタイムどう書くの参考問題をRubyで解く

問題はこちらのリンクから。
http://qiita.com/Nabetani/items/89fb0e2e712d4b396535

全探索なので遅いです。

def solve(q)
  target = q.to_i
  done = {0=>0}
  cur = [0]
  (1..target).each{|nest|
    nxt = []
    cur.each{|num|
      if done[num - 1].nil?
        done[num - 1] = nest
        nxt << num - 1
      end
      if done[num + 1].nil?
        done[num + 1] = nest
        nxt << num + 1
      end
      if done[num * 2].nil?
        done[num * 2] = nest
        nxt << num * 2
      end
    }
    return nest if nxt.include?(target) 
    cur = nxt
  }
  -1
end

DATA.readlines.each do |line|
  no,q,a,*s = line.chop.split(/\s+/)
  ans = solve(q)
  print no + "\t" + ans.to_s
  puts ans == a.to_i ? ' o' : ' x'
end
__END__
0   59  9    +1 ×2 ×2 ×2 ×2 -1 ×2 ×2 -1
1   10  5    +1 +1 ×2 +1 ×2
2   11  6    +1 ×2 ×2 +1 ×2 +1