CodeIQ：切手を切って！
私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「切手を切って！」（CodeIQ）を参照してください。
問題の概要
次のような切手シートがあります。
この切手シートから、3枚の切手がつながったまま切り取る方法は、以下のように10通りあります。
【問題】
切手シートの、たて・よこ・切り取りたい枚数が与えられたとき、切り取り方の総数を求めてください。
たて・よこの枚数は、いずれも1～10枚、切り取りたい枚数は1～5枚を想定してください。
【入力】
次の書式で数値が与えられます。
●1行目に、データセットの件数nが書かれています。
●2行目以降のn行に、たての枚数・よこの枚数・切り取りたい切手の枚数が、半角スペースで区切られています。
----（例）----
2
2 3 2
2 3 3
----（例）----
【出力】
データセット毎に、改行区切りで切手の切り取り方が何通りあるかを出力してください。
----（例）----
7
10
----（例）----
私のプログラム
Rubyで解答しています。
#!/usr/bin/ruby
PTN = [
nil,
[
[[0,0]]
],
[
[[0,0],[0,1]],
[[0,0],[1,0]]
],
[
# I
[[0,0],[0,-1],[0,1]],
[[0,0],[-1,0],[1,0]],
# L
[[0,0],[0,-1],[-1,0]],
[[0,0],[0,-1],[1,0]],
[[0,0],[0,1],[-1,0]],
[[0,0],[0,1],[1,0]],
],
[
# I
[[0,0],[0,1], [0,2], [0,3]],
[[0,0],[1,0], [2,0], [3,0]],
# L右
[[0,0],[0,1], [0,2], [1,2]],
[[0,0],[1,0], [2,0], [0,1]],
[[0,0],[1,0], [1,1], [1,2]],
[[0,0],[1,0], [2,0], [2,-1]],
# L左
[[0,0],[0,1], [0,2], [-1,2]],
[[0,0],[1,0], [2,0], [0,-1]],
[[0,0],[0,1], [0,2], [1,0]],
[[0,0],[1,0], [2,0], [2,1]],
# O
[[0,0],[1,0], [0,1], [1,1]],
# S(Z)
[[0,0],[1,0], [1,1], [2,1]],
[[0,0],[0,1], [-1,1], [-1,2]],
[[0,0],[1,0], [1,-1], [2,-1]],
[[0,0],[0,1], [1,1], [1,2]],
# T
[[0,0],[0,1], [0,2], [-1,1]],
[[0,0],[-1,1], [0,1], [1,1]],
[[0,0],[0,1], [0,2], [1,1]],
[[0,0],[1,0], [2,0], [1,1]],
],
[
[[0,0],[0, 1], [0, 2], [0, 3], [0, 4]],
[[0,0],[0, 1], [0, 2], [0, 3], [1, 2]],
[[0,0],[0, 1], [0, 2], [0, 3], [1, 3]],
[[0,0],[0, 1], [0, 2], [0, 3], [1, 1]],
[[0,0],[0, 1], [0, 2], [1, 1], [1, 2]],
[[0,0],[0, 1], [0, 2], [1, 1], [2, 1]],
[[0,0],[0, 1], [0, 2], [1, 2], [1, 3]],
[[0,0],[0, 1], [0, 2], [1, 2], [2, 2]],
[[0,0],[0, 1], [0, 2], [0, 3], [1, 0]],
[[0,0],[0, 1], [0, 2], [1, -1], [1, 0]],
[[0,0],[0, 1], [0, 2], [1, 0], [1, 1]],
[[0,0],[0, 1], [0, 2], [1, 0], [1, 2]],
[[0,0],[0, 1], [0, 2], [1, 0], [2, 0]],
[[0,0],[0, 1], [1, -2], [1, -1], [1, 0]],
[[0,0],[0, 1], [1, -1], [1, 0], [2, -1]],
[[0,0],[0, 1], [1, -1], [1, 0], [2, 0]],
[[0,0],[0, 1], [1, -1], [1, 0], [1, 1]],
[[0,0],[0, 1], [1, 0], [1, 1], [1, 2]],
[[0,0],[0, 1], [1, 0], [1, 1], [2, 0]],
[[0,0],[0, 1], [1, 0], [1, 1], [2, 1]],
[[0,0],[0, 1], [1, 0], [2, -1], [2, 0]],
[[0,0],[0, 1], [1, 0], [2, 0], [2, 1]],
[[0,0],[0, 1], [1, 0], [2, 0], [3, 0]],
[[0,0],[0, 1], [1, 1], [1, 2], [1, 3]],
[[0,0],[0, 1], [1, 1], [1, 2], [2, 1]],
[[0,0],[0, 1], [1, 1], [1, 2], [2, 2]],
[[0,0],[0, 1], [1, 1], [2, 0], [2, 1]],
[[0,0],[0, 1], [1, 1], [2, 1], [2, 2]],
[[0,0],[0, 1], [1, 1], [2, 1], [3, 1]],
[[0,0],[1, -3], [1, -2], [1, -1], [1, 0]],
[[0,0],[1, -2], [1, -1], [1, 0], [2, -2]],
[[0,0],[1, -2], [1, -1], [1, 0], [2, -1]],
[[0,0],[1, -2], [1, -1], [1, 0], [1, 1]],
[[0,0],[1, -1], [1, 0], [1, 1], [1, 2]],
[[0,0],[1, -1], [1, 0], [1, 1], [2, -1]],
[[0,0],[1, -1], [1, 0], [1, 1], [2, 0]],
[[0,0],[1, -1], [1, 0], [1, 1], [2, 1]],
[[0,0],[1, -1], [1, 0], [2, -2], [2, -1]],
[[0,0],[1, -1], [1, 0], [2, -1], [3, -1]],
[[0,0],[1, -2], [1, -1], [1, 0], [2, 0]],
[[0,0],[1, -1], [1, 0], [2, -1], [2, 0]],
[[0,0],[1, -1], [1, 0], [2, 0], [2, 1]],
[[0,0],[1, -1], [1, 0], [2, 0], [3, 0]],
[[0,0],[0, 2], [1, 0], [1, 1], [1, 2]],
[[0,0],[1, 0], [1, 1], [1, 2], [1, 3]],
[[0,0],[1, 0], [1, 1], [1, 2], [2, 1]],
[[0,0],[1, 0], [1, 1], [1, 2], [2, 2]],
[[0,0],[1, 0], [1, 1], [1, 2], [2, 0]],
[[0,0],[1, 0], [1, 1], [2, -1], [2, 0]],
[[0,0],[1, 0], [1, 1], [2, 0], [2, 1]],
[[0,0],[1, 0], [1, 1], [2, 0], [3, 0]],
[[0,0],[1, 0], [1, 1], [2, 1], [2, 2]],
[[0,0],[1, 0], [1, 1], [2, 1], [3, 1]],
[[0,0],[1, 0], [2, -2], [2, -1], [2, 0]],
[[0,0],[1, 0], [2, -1], [2, 0], [2, 1]],
[[0,0],[1, 0], [2, -1], [2, 0], [3, -1]],
[[0,0],[1, 0], [2, -1], [2, 0], [3, 0]],
[[0,0],[1, 0], [2, 0], [2, 1], [2, 2]],
[[0,0],[1, 0], [2, 0], [2, 1], [3, 0]],
[[0,0],[1, 0], [2, 0], [2, 1], [3, 1]],
[[0,0],[1, 0], [2, 0], [3, -1], [3, 0]],
[[0,0],[1, 0], [2, 0], [3, 0], [3, 1]],
[[0,0],[1, 0], [2, 0], [3, 0], [4, 0]],
]
]
def inGrid?(ptn, i, j, r, c)
for g in ptn
y = i + g[0]
x = j + g[1]
return 0 if (x < 0) || (y < 0) || (c <= x) || (r <= y)
end
return 1
end
def check(ptn, r, c)
ret = 0
for i in 0...r
for j in 0...c
ret += inGrid?(ptn, i, j, r, c)
end
end
return ret
end
def solve(r, c, n)
ret = 0
for ptn in PTN[n]
ret += check(ptn, r, c)
end
return ret
end
# main
STDIN.each_line.with_index{|line, i|
next if i == 0
line.strip!
next if line.empty?
r, c, n = line.split.map{|v| v.to_i}
p solve(r, c, n)
}
解説
真面目にやると相当難しいです。
私は真面目にやりませんでした。
考え方
連続した切手の形状はポリオミノになります。
ポリオミノを構成する任意の切手の座標を(0,0)とした場合に、他の切手の場所を相対座標として列挙します。
切手シートの任意の位置に対して(0,0)の座標の切手を配置した場合にポリオミノを構成する他の切手がシート内に収まるかどうかを調べれば良いわけです。
ただし、難しいのはポリオミノの列挙です。
私は最初に定数で列挙してしまいました。
main
入力値を数値にしてsolve()に渡します。
定数PTNはn枚の切手でできるポリオミノ（回転や反転したパターンを別物とした全パターン）です。
solve(a, e)
n枚でできるポリオミノ全パターンに対してchekc()を呼び、シート内に収まるパターンがいくつあるかを求めます。
全パターンに対しての結果を加算したものが答えなのでそれを返します。
check(ptn, r, c)
シートの全座標に対してはみ出さずにポリオミノ状の配置が収まるかを調べます。
isGrid?()はポリオミノの(0,0)の位置をシートの(i,j)に取った時、(r,c)の範囲に収まるかを調べます。rはシートの行数、cは列数です。
isGrid?()は収まるなら1、収まらないなら0を返すのでそれを加算すれば収まる開始座標位置の数になります。
inGrid?(ptn, i, j, r, c)
ポリオミノの(0,0)の位置をシートの(i,j)に取った時、(r,c)の範囲に収まるかを調べます。
ptnはポリオミノの形状です。
iはポリオミノの(0,0)の切手の行番号、jは列番号です。
rはシートの行数、cは列数です。
ptn内の全ての相対座標がシート内にあれば1、1つでも無ければ0を返します。
雑感
ポリオミノの列挙が難しいです。
これ、n≧6まで対応しなければならなかった場合は私がやったみたいにあらかじめ列挙しておくことが困難になります。そうすると★★のレベルでは無いと思います。