上と左の合計(再帰)

本番で書いた汚いコードはこちら。http://qiita.com/cielavenir/items/ab6c3e9a482c7b42519e

本番中に再帰は考えていたものの、焦ってしまい実装に手が回らなかった。

律儀にclassとしたが、Rubyはmainインスタンスにインスタンス変数を追加できるので必要ではなかったかもしれない。

hena22_rec.rb

#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/34bf2a05099a47e193b6
#http://nabetani.sakura.ne.jp/hena/ord22irrpas/
class Hena22
    def initialize(cells)
        @cells=cells
        @memo={}
    end
    def solve(x,y)
        return 0 if x<0||y<0
        return 1 if x==0&&y==0
        if @memo[[x,y]]
            return @memo[[x,y]]
        end
        cell=@cells.find{|e|e[:x1]<=x&&x<e[:x2] && e[:y1]<=y&&y<e[:y2]}
        if cell
            if cell[:x1]==x && cell[:y1]==y
                cells_for_val={}
                val=0
                (cell[:y1]...cell[:y2]).each{|_y|
                    adjacent_cell=@cells.find{|e|e[:x1]<=x-1&&x-1<e[:x2] && e[:y1]<=_y&&_y<e[:y2]}
                    if !adjacent_cell||!cells_for_val.include?(adjacent_cell)
                        cells_for_val[adjacent_cell]=1 if adjacent_cell
                        val+=solve(x-1,_y)
                    end
                }
                (cell[:x1]...cell[:x2]).each{|_x|
                    adjacent_cell=@cells.find{|e|e[:x1]<=_x&&_x<e[:x2] && e[:y1]<=y-1&&y-1<e[:y2]}
                    if !adjacent_cell||!cells_for_val.include?(adjacent_cell)
                        cells_for_val[adjacent_cell]=1 if adjacent_cell
                        val+=solve(_x,y-1)
                    end
                }
                return @memo[[x,y]]=val
            else
                return @memo[[x,y]]=solve(cell[:x1],cell[:y1])
            end
        else
            return @memo[[x,y]]=solve(x-1,y)+solve(x,y-1)
        end
    end
end

if $0==__FILE__
    STDOUT.sync=true
    while gets
        a,b=$_.chomp.split(':')
        column,row=a.split('x').map(&:to_i)
        cells=!b ? [] : b.split(',').map{|e|
            l,t,w,h=e.split('').map(&:to_i)
            #高さ/幅から端点の座標に変更
            {:x1=>l.to_i,:x2=>l.to_i+w.to_i,:y1=>t.to_i,:y2=>t.to_i+h.to_i}
        }
        puts '%02d'%[Hena22.new(cells).solve(column-1,row-1)%100]
    end
end