Submission #31297214

---

Source Code Expand

macro make_array(value, *dims)
  {% for dim in dims %} Array.new({{dim}}) { {% end %}
    {{ value }}
  {% for dim in dims %} } {% end %}
end

h, w = gets.to_s.split.map(&.to_i)
s = Array.new(h) { gets.to_s }

sy = sx = gy = gx = -1
g = Array.new(h) do |y|
  Array.new(w) do |x|
    case s[y][x]
    when '1'..'9'
      s[y][x].to_i
    when 's'
      sy = y
      sx = x
      0
    when 'g'
      gy = y
      gx = x
      10000000 # ゴールは無条件で進めるほど明るい
    when '#'
      -1
    else
      raise "bad input #{s[y][x]}"
    end
  end
end

pr = Problem.new(h, w, g, sy, sx, gy, gx)
ans = pr.solve
pp ans == 0.0 ? -1 : ans

class Problem
  DIR = [{-1, 0}, {0, -1}, {1, 0}, {0, 1}]
  INF = 1e9.to_i64
  getter h : Int32
  getter w : Int32
  getter g : Array(Array(Int32))
  getter sy : Int32
  getter sx : Int32
  getter gy : Int32
  getter gx : Int32

  def initialize(@h, @w, @g, @sy, @sx, @gy, @gx)
  end

  def solve
    lo = 0.0
    hi = 10.0
    (lo..hi).bsearch do |v|
      !query(v)
    end
  end

  # 明るさvを保ったままゴールできるか
  def query(v)
    depth = make_array(INF, h, w)
    depth[sy][sx] = 0
    seen = make_array(false, h, w)
    seen[sy][sx] = true
    q = Deque.new([{sy, sx}])
    while q.size > 0
      y, x = q.shift
      break if y == gy && x == gx
      each(y, x) do |ny, nx|
        next if wall?(ny, nx)
        next if seen[ny][nx]
        seen[ny][nx] = true
        t = depth[y][x] + 1
        next if g[ny][nx] * 0.99 ** t < v
        depth[ny][nx] = t
        q << {ny, nx}
      end
    end
    depth[gy][gx] != INF
  end

  def outside?(y, x)
    y < 0 || h <= y || x < 0 || w <= x
  end

  def wall?(y, x)
    g[y][x] == -1
  end

  def each(y, x)
    DIR.each do |dy, dx|
      ny = y + dy
      nx = x + dx
      next if outside?(ny, nx)
      yield ny, nx
    end
  end
end

Submission Info

Judge Result