池の数を数えるプログラム

池の数を数えるプログラム.rb

data =<<END
水土土土土土土土土水水土
土水水水土土土土土水水水
土土土土水水土土土水水土
土土土土土土土土土水水土
土土土土土水土土土水土土
土土水土土土土土土水土土
土水土水土土土土土水水土
水土水土水土土土土土水土
土水土水土土土土土土水土
土土水土土土土土土土水土
END

data =<<END
土土土土土土土土土土土土
土水土土水土土水水土土土
土水土土水土水土土水土土
土土水水土土水土土水土土
土土土土土土土土土土土土
土水水土土土水水土土水土
土土土水土水土土土水土水
土土土水土水土土土水土水
土水水土土土水水土土水土
土土土土土土土土土土土土
END

def dump_ponds(data, ponds)
  data.split.each_with_index do |row, y|
    row.each_char.with_index do |c, x|
      print ponds[[x, y]] || '-'
    end
    puts
  end
  puts
end

max = 0
ponds = {}
ds = [[-1, 0], [-1, -1], [0, -1], [1, -1]]

data.split.each_with_index do |row, y|
  row.each_char.with_index do |c, x|
    next unless c == '水'

    ns = ds.map { |dx, dy| ponds[[x + dx, y + dy]] }
    ns.delete(nil)

    if ns.empty?
      max += 1
      ponds[[x, y]] = max
    else
      n, *xs = ns
      xs.each do |x|
        ponds.each do |pos, val|
          ponds[pos] = n if val == x
        end
      end
      ponds[[x, y]] = n
    end

    # dump_ponds(data, ponds)
  end
end

# dump_ponds(data, ponds)
p ponds.values.uniq.size