Submission #365606

---

Source Code Expand

Map = Struct.new(:m, :h, :w, :t) do
  def dijkstra(start, goal)
    tree = {start => [0, nil, nil]}
 
    loop do
      u, ui = tree.min {|(_,a),(_,b)| a.size == 2 ? 1 : b.size == 2 ? -1 : a[0] <=> b[0] }
      break if ui.size != 3 || u == goal
      ui.pop
 
      ud = ui[0]
      each_neighbor(u) do |n|
        alt = ud + yield(u, n)
        t = tree[n]
 
        if t.nil?
          tree[n] = [alt, u, nil]
        elsif alt < t[0]
          t[0] = alt
          t[1] = u
        end
      end
    end
 
    tree
  end
 
  def each_neighbor(node)
    y, x = node.divmod(w)
    yield node - 1 if x > 0
    yield node + 1 if x < w - 1
    yield node - w if y > 0
    yield node + w if y < h - 1
  end
 
  def solve
    mm = m.join
    z = mm.size
    s = mm.index('S')
    g = mm.index('G')
    (1..t).bsearch {|x|
      paths = dijkstra(s, g) {|u, n| mm.getbyte(n) == 35 ? x : 1 }
      t < paths[g][0]
    } - 1
  end
end
 
i=STDIN
h,w,t=i.gets.split.map(&:to_i)
m=(1..h).map{i.gets.chomp}
p Map.new(m, h, w, t).solve

Submission Info

Compile Error

./Main.rb:37: warning: assigned but unused variable - z

Judge Result