Submission #1071239

---

Source Code Expand

H, W = gets.split.map(&:to_i)
As = [[0] * (W + 2)] + readlines.map{|l| [0] + l.split.map(&:to_i) + [0]} + [[0] * (W + 2)]
MOD = 1_000_000_007

def dp(i, j)
  return @dp[i][j] if @dp[i][j]
  ret, a = 1, As[i][j]
  ret += dp(i + 1, j) if As[i + 1][j] > a
  ret += dp(i - 1, j) if As[i - 1][j] > a
  ret += dp(i, j + 1) if As[i][j + 1] > a
  ret += dp(i, j - 1) if As[i][j - 1] > a
  @dp[i][j] = ret
end

@dp = Array.new(H + 2){Array.new(W + 2, nil)}
ans = 0
(1 .. H).each do |i|
  (1 .. W).each do |j|
    ans = (ans + dp(i, j)) % MOD
  end
end
puts ans

Submission Info

Judge Result