paiza オンラインハッカソン vol.2 の解説アルゴリズムで

poh2.rb

height, width = gets.split.map(&:to_i)
window = []
height.times {window << gets.chomp.chars.map(&:to_i)}
num = gets.to_i
wgtsize = []
num.times {wgtsize << gets.split.map(&:to_i)}

height.times do |h|
  (width  - 1).times {|w| window[h][w + 1] += window[h][w]}
end
width .times do |w|
  (height - 1).times {|h| window[h + 1][w] += window[h][w]}
end

num.times do
  h, w = wgtsize.shift
  co = 0
  (height - h + 1).times do |i|
    (width - w + 1).times do |j|
      h1, w1 = h + i - 1, w + j - 1
      a1 = window[h1][w1 - w]
      a2 = window[h1 - h][w1]
      a3 = window[h1 - h][w1 - w]
      a2 = a3 = 0 if i.zero?
      a1 = a3 = 0 if j.zero?
      s = window[h1][w1] - a1 - a2 + a3
      co += 1 if s.zero?
    end
  end
  puts co
end