Submission #750666

---

Source Code Expand

# 下記の改変
# http://abc037.contest.atcoder.jp/submissions/750568
 
class Keiro
  MOD = 100_000_007
 
  def initialize(h, w, grid)
    @h = h
    @h2 = h + 2
    @w = w
    @w2 = w + 2
    # @gridと@combは1次元
    @grid = grid
    @comb = Array.new(@h2 * @w2, nil)
    # @nexts = [-1, 1, -@w2, @w2]
  end
 
  def dfs(ij)
    # 動かない場合もあるのでres=1
    res = 1
    # 何度も呼ぶのは1度だけにする
    gij = @grid[ij]
    # 既に探索した木ならその値を返す
    #return @comb[i][j] if @comb[i][j]>0
    return @comb[ij] if @comb[ij]>0
    # 上下左右のほうが大きければ移動する
    # 上下左右への計算も工夫
    # @nexts.each do |x|
    #   x += ij
    #   res += @comb[x] || dfs(x) if gij < @grid[x]
    # end
    # res += @comb[ij - 1] || dfs(ij - 1) if gij < @grid[ij - 1]
    # res += @comb[ij + 1] || dfs(ij + 1) if gij < @grid[ij + 1]
    # res += @comb[ij - @w2] || dfs(ij - @w2) if gij < @grid[ij - @w2]
    # res += @comb[ij + @w2] || dfs(ij + @w2) if gij < @grid[ij + @w2]
    x = ij - 1
    res += @comb[x] || dfs(x) if gij < @grid[x]
    x = ij + 1
    res += @comb[x] || dfs(x) if gij < @grid[x]
    x = ij - @w2
    res += @comb[x] || dfs(x) if gij < @grid[x]
    x = ij + @w2
    res += @comb[x] || dfs(x) if gij < @grid[x]
 
    # 移動経路数を2次元配列に格納し、値を返す
    # Array#[]で呼び直さない
    # res %= MOD
    @comb[ij] = res
    res
  end
 
  def dfs_each
    ij = @w2 + 1
    @h.times do
      @w.times do
        yield (@comb[ij] || dfs(ij))
        ij += 1
      end
      ij += 2
    end
  end
end
 
# 高さ、幅の読み取り
h, w = gets.chomp.split.map(&:to_i)
# マス目を格納する2次元配列及び、経路数を格納する2次元配列を用意
grid = []
# 最初
grid.concat(Array.new(w + 2, 0))
# マス目のよみとり
h.times do
  grid << 0
  grid.concat(gets.split.map(&:to_i))
  grid << 0
end
# 最後
grid.concat(Array.new(w + 2, 0))
 
keiro = Keiro.new(h, w, grid)
 
ans = 0
keiro.dfs_each do |dfs|
  ans += dfs
  # MODより大きければ引く
  # ans %= Keiro::MOD
  # ans -= Keiro::MOD if ans > Keiro::MOD
end
 
puts(ans % Keiro::MOD)

Submission Info

Judge Result