Jamilson, dessa vez sozinho, foi a um parque de
diversão. Resolveu experimentar um novo brinquedo, o Divide and
Conquer. Basicamente esse brinquedo consiste em separar um grupo
de peças em dois subgrupos de forma que nenhuma peça possa se encaixar
com as peças de seu grupo. Uma peça se encaixa em outra se ao juntá-las
elas formam um retângulo com length <=
L e weight <=
W.
O problema aqui é ajudar Jamilson mostrando 2
grupos (entre possíveis vários grupos) de peças que satisfaçam o critério
acima, dado um grupo de peças iniciais. As peças não podem ser rodadas, só
transladadas.
A entrada consiste de vários conjuntos de dados.
Cada conjunto de dados contêm 3 inteiros 0 < (L, W, N) <= 100 e
N peças sucessivas.
Uma peça consiste em 1 número (T <= L) indicando quantidade de linhas
que possui (uma linha nunca terá tamanho maior que W).
Seguem pra cada peça N linhas com símbolos quando existe algo da peça naquela
posição.
A saída consiste, para cada conjunto de dados, em dois grupos de peças.
Cada grupo possui um inteiro em uma linha (indicando quantas peças existem
naquele grupo), seguido das descrições das peças (a mesma da entrada).
3 4 9 3 oooo oooo ooo 3 oo ooo oooo 3 oooo o o oooo 3 o oo ooo 3 oooo oo o oooo 2 oo o 2 oo oo 1 o 3 oooo ooo ooo
Conjunto #1: 5 3 oooo oooo ooo 3 oooo o o oooo 3 oooo oo o oooo 2 oo o 3 oooo ooo ooo 4 3 oo ooo oooo 3 o oo ooo 2 oo oo 1 o