Submission #882240

---

Source Code Expand

if !ENV['RUBY_THREAD_VM_STACK_SIZE']
  exec({'RUBY_THREAD_VM_STACK_SIZE'=>'1000000000'}, '/usr/bin/ruby', $0)
else
  def get_path_count(y, x)
    count = 1
    value = $field[y][x]
 
    if value < $field[y][x-1]
      count += $cache[y][x-1] || get_path_count(y, x-1)
      count -= $mod if count >= $mod
    end
 
    if value < $field[y][x+1]
      count += $cache[y][x+1] || get_path_count(y, x+1)
      count -= $mod if count >= $mod
    end
 
    if value < $field[y-1][x]
      count += $cache[y-1][x] || get_path_count(y-1, x)
      count -= $mod if count >= $mod
    end
 
    if value < $field[y+1][x]
      count += $cache[y+1][x] || get_path_count(y+1, x)
      count -= $mod if count >= $mod
    end
 
    $cache[y][x] = count
  end
 
  $mod = 1000000007
  height, width = gets.split.map(&:to_i)
  $field = []
 
  $cache = Array.new(height+2).map{ Array.new(width+2) }
 
  $field << [0]*(width+2)
  height.times do
    $field << ("0 "+gets+" 0").split.map(&:to_i)
  end
  $field << [0]*(width+2)
 
  path_count = 0
 
  (1..height).each do |y|
    (1..width).each do |x|
      path_count += $cache[y][x] || get_path_count(y, x)
      path_count -= $mod if path_count>=$mod
    end
  end
 
  puts path_count
end

Submission Info

Judge Result