http://icpc2010.honiden.nii.ac.jp/domestic-contest/problems#section_B

gistfile1.rb

class Maze
  def initialize(w,h,input)
    @len_map = Hash.new
    @len_map[[w-1,h-1]] = 1
    make_fence(input)
  end

  def make_fence(input)
    lr, tb = [], []
    input.each_with_index do |e,i|
      e.map!{|c| c==1 ? false : true}
      lr << e if i.even?
      tb << e if i.odd?
    end
    @lr = lr.map{|e| [false,e,false].flatten}
    @tb = tb.transpose.map{|e| [false,e,false].flatten}
  end

  def cell(i,j)
    [@tb[i][j], @lr[j][i+1], @tb[i][j+1], @lr[j][i]]
  end

  def length
    count = 1
    until @len_map[[0,0]]
      s = @len_map.select{|k,v| v == count}
      break if s.size == 0
      count += 1
      s.each do |k,v|
        i,j = k[0], k[1]
        w = cell(i,j)
        @len_map[[i,j-1]] = count if w[0] && !@len_map[[i,j-1]]
        @len_map[[i,j+1]] = count if w[2] && !@len_map[[i,j+1]]
        @len_map[[i+1,j]] = count if w[1] && !@len_map[[i+1,j]]
        @len_map[[i-1,j]] = count if w[3] && !@len_map[[i-1,j]]
      end
     end
    @len_map[[0,0]] || 0
  end
end

inputs = File.open('input.txt').map do |l|
  l.split.map{|e| Integer(e)}
end

until inputs.empty?
  w, h = inputs.shift
  break if w==0 and h==0
  input = []
  (h*2-1).times do input << inputs.shift end
  m = Maze.new(w,h,input)
  p m.length
end