#1497547

Solution for 0558: Cheese by iwamot

Source Code Status Test Cases
    Policy: public     Reviewed: 86    
13.14 sec    208056 KB    50 lines     854 bytes    2015-08-30 19:30
def bfs(n)
  si, sj = $pos[n - 1]
  gi, gj = $pos[n]

  secs = {"#{si},#{sj}" => 0}
  q = [[si, sj]]

  mv = [[0, 1], [0, -1], [1, 0], [-1, 0]]
  while pos = q.shift
    ci, cj = pos
    return secs["#{ci},#{cj}"] if ci == gi && cj == gj

    mv.each do |mi, mj|
      ni = ci + mi
      next if ni < 0 || ni >= $h
      nj = cj + mj
      next if nj < 0 || nj >= $w

      next if secs["#{ni},#{nj}"] || $map[ni][nj] == 'X'

      secs["#{ni},#{nj}"] = secs["#{ci},#{cj}"] + 1
      q.push [ni, nj]
    end
  end
end

$h, $w, $n = gets.split(' ').map(&:to_i)

$map = []
$pos = {}
0.upto($h - 1) do |i|
  $map[i] = gets.chomp.split(//)
  0.upto($w - 1) do |j|
    case $map[i][j]
    when 'S'
      $pos[0] = [i, j]
    when 'X', '.'
    else
      $pos[$map[i][j].to_i] = [i, j]
    end
  end
end

ans = 0
1.upto($n) do |n|
  ans += bfs(n)
end
puts ans


Compile Error Logs:
You are not authorized to see the message.

Status
Judge: 5/5 Ruby CPU: 13.14 sec Memory: 208056 KB Length: 854 B 2015-08-30 19:30 2015-08-30 19:30
Results for testcases
Case # Verdict CPU Time Memory In Out Case Name
Case #1: : Accepted 00.05 sec 8660 KB
Case #2: : Accepted 00.05 sec 8760 KB
Case #3: : Accepted 00.08 sec 8952 KB
Case #4: : Accepted 13.14 sec 208056 KB
Case #5: : Accepted 02.76 sec 103676 KB
< prev | / | next >  
 
Judge Input #  ( | ) Judge Output #  ( | )


Comments
 
 Under Construction.
 
Categories
 
 
Free Tags