上と左の合計

http://qiita.com/Nabetani/items/34bf2a05099a47e193b6
http://nabetani.sakura.ne.jp/hena/ord22irrpas/

50分ほど。かなり大変でした。
一応Ruby 1.8/2.0で動作。
nilを活用しているので同等のものがない言語への移植は困難。

hena22.rb

#!/usr/bin/env ruby
#http://qiita.com/Nabetani/items/34bf2a05099a47e193b6
#http://nabetani.sakura.ne.jp/hena/ord22irrpas/
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)
        #番兵を設けるため1を足す。高さ/幅から端点の座標に変更。
        {:x1=>l.to_i+1,:x2=>l.to_i+1+w.to_i,:y1=>t.to_i+1,:y2=>t.to_i+1+h.to_i}
    }

    m=(row+1).times.map{[nil]*(column+1)}
    (row+1).times{|y|m[y][0]=0}
    (column+1).times{|x|m[0][x]=0}
    m[0][1]=1 #m[1][0]=1でも可。適当。

    while !m[row][column] # 右下が埋まるまで
        1.step(row){|y|
            1.step(column){|x|
                next if m[y][x] # 既に埋まっていたらスキップ
                #1x1のセルでなければ
                if cell=cells.find{|e|e[:x1]<=x&&x<e[:x2] && e[:y1]<=y&&y<e[:y2]}
                    #セルの右上を見ている時に限り左・上隣を見る
                    if cell[:x1]==x && cell[:y1]==y
                        cells_for_val={}
                        val=0
                        #左隣
                        unless (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
                                break if !m[_y][x-1] # まだセルが埋まっていなければスキップ。breakするとeachはnilを返す。unless〜next。
                                val+=m[_y][x-1]
                            end
                        }
                            next
                        end
                        #上隣
                        unless (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
                                break if !m[y-1][_x]
                                val+=m[y-1][_x]
                            end
                        }
                            next
                        end
                        #セルを埋める
                        (cell[:y1]...cell[:y2]).each{|_y|
                            (cell[:x1]...cell[:x2]).each{|_x|
                                m[_y][_x]=val%100
                            }
                        }
                    end
                else
                    next if !m[y-1][x] || !m[y][x-1]
                    val=m[y-1][x]+m[y][x-1]
                    m[y][x]=val%100
                end
            }
        }
    end
    puts "%02d"%m[row][column]
end