CodeIQ：縦線と横線でマス目を塗る

問題の概要

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 入力値をパースする
def parseLine(line)
	vs = []
	hs = []

	splited = line.split
	for s in splited
		prm = s.split(",").map{|a| a =~ /[0-9]+/ ? a.to_i: a}
		if prm[0] == "V" then vs << prm
		elsif prm[0] == "H" then hs << prm
		end
	end

	return vs, hs
end

# 同じ向きの2つの線ので繋げられるものを繋ぐ
# p1,p2はVの場合[y, len]、Hの場合[x, len]
def joinLine(p1, p2)
#	printf("p1=%s, p2=%s\n", p1.to_s, p2.to_s)	# DEBUG
	st = [p1[0], p2[0]].min
	ed = [p1[0]+p1[1], p2[0]+p2[1]].max

	len1 = p1[1] + p2[1]	# 実際の線の長さ
	len2 = ed - st			# 2つの線の両端の長さ
#	printf("len1=%d, len2=%d\n", len1, len2)	# DEBUG

	# 両端の長さが実際の線の長さより長ければ重なっていたりしない
	if len2 > len1 then return nil
	else return [st, len2]
	end
end

# Vでx座標が同じものを繋げられるなら繋げて一つのデータにする
def joinVsameX(org)
	vs = org.sort{|a, b| a[2] <=> b[2]}	# y座標の順にソート
#	printf("vs=%s\n", vs.to_s)	# DEBUG
	ret = []
	ret << vs.shift

	while !vs.empty?
		nv = vs.shift

		hold = nv
		for i in 0...ret.size
			joined = joinLine([ret[i][2], ret[i][3]], [nv[2], nv[3]])
			if joined != nil then
				ret[i] = [ret[i][0], ret[i][1], joined[0], joined[1]]
				hold = nil
				break
			end
		end

		if hold != nil then ret << hold end

#		printf("ret=%s\n", ret)	# DEBUG
	end

	return ret
end

# Vをx座標が同じもので分ける
def groupV(org)
	ret = {}

	for o in org
		x = o[1]
		if ret[x] == nil then ret[x] = [] end
		ret[x] << o
	end

	return ret
end

# Vでx座標が同じもので重なっているか繋がるものを繋げる
def joinV(vs)
	vg = groupV(vs)
	ret = []

	vg.each{|_, arr|
#		printf("target => %s\n", arr)	#DEBUG
		ret += joinVsameX(arr)
	}

	return ret
end

# Hでy座標が同じものを繋げられるなら繋げて一つのデータにする
def joinHsameY(org)
	hs = org.sort{|a, b| a[1] <=> b[1]}	# x座標の順にソート
#	printf("hs=%s\n", hs.to_s)	# DEBUG
	ret = []
	ret << hs.shift

	while !hs.empty?
		nh = hs.shift

		hold = nh
		for i in 0...ret.size
			joined = joinLine([ret[i][1], ret[i][3]], [nh[1], nh[3]])
			if joined != nil then
				ret[i] = [ret[i][0], joined[0], ret[i][2], joined[1]]
				hold = nil
				break
			end
		end

		if hold != nil then ret << hold end

#		printf("ret=%s\n", ret)	# DEBUG
	end

	return ret
end

# Hをy座標が同じもので分ける
def groupH(org)
	ret = {}

	for o in org
		y = o[2]
		if ret[y] == nil then ret[y] = [] end
		ret[y] << o
	end

	return ret
end

# Hでy座標が同じもので重なっているか繋がるものを繋げる
def joinH(hs)
	hg = groupH(hs)
	ret = []

	hg.each{|_, arr|
#		printf("target => %s\n", arr)	#DEBUG
		ret += joinHsameY(arr)
	}

	return ret
end

# 重複を含めて塗りつぶされた座標を数える
def countBlack(lines)
	ret = 0
	for l in lines
		ret += l[3]
	end
	return ret
end

# 重複箇所を数える
def countCrossed(vs, hs)
	ret = 0
	for v in vs
		y_min = v[2]
		y_max = v[2] + v[3] - 1

		for h in hs
			x_min = h[1]
			x_max = h[1] + h[3] - 1
			if ((y_min <= h[2]) && (h[2] <= y_max)) && ((x_min <= v[1]) && (v[1] <= x_max))then ret += 1 end
		end
	end
	return ret
end

# 問題を解く
def solve(line)
	vs, hs = parseLine(line)
	jv = joinV(vs)
	jh = joinH(hs)

	ret = countBlack(jv) + countBlack(jh) - countCrossed(jv, jh)
	return ret
end

# main
while line = gets
	line.strip!
	if line.empty? then next end

	p solve(line)
end

解説

見た目よりも難しいと思います。ただ、頑張ればできるタイプの問題です。

雑感

線をわざわざ繋げないで重なった部分だけをカウントするうまい方法がありそうな気もします。
話は変わりますが、「〜〜H()」、「〜〜V()」の関数はだいたい同じ処理なのでまとめようと思えばまとめられます（引数を増やしてx座標かy座標の要素番号を渡せば良い）。ただ、わかりやすさにはあまり寄与しないと思うのです。あとで見たときに「この引数はなんだっけ？」と一旦考えないといけないのが面倒というか。
でも、3つ以上になったらさすがにまとめてしまうので、やはりまとめるべきだったかもしれません。