PKU 1448 - Cube

Autor da análise: MarchettiMarchetti

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1448

Resumo

Dadas 6 matrizes 6x6 de caracteres representando peças, decidir se é possível organizá-las como "faces" de um cubo como naquele relativamente famoso joguinho de encaixar…
Entendemos que cada candidato a face, ou peça, tem uma espessura constante e a matriz que a representa mostra o formato das peças descrevendo as outras duas dimensões da seguinte forma:
Cada caractere é um ponto "." ou um xis "X".
A peça é como um corte em uma placa sólida de mesma espessura e dividida em uma grade 6x6.
Um xis representa que a peça é sólida, ou contém volume, no cubo definido pela posição na grade igual a posição do caractere na matriz.
Um ponto representa o contrário, ou seja, que a peça não contém aquele cubo.
Essa representação é um tanto natural então não vou explicar mais…

O enunciado diz que a matriz central 5x5, o miolo da grade para cada peça, de cada matriz 6x6 é preenchida por "X".

Solução

Uma possível solução para esse problema, pelo menos é a que eu enxerguei, é resolvê-lo por backtracking.
Explicando melhor, dadas as 6 peças devemos tentar todos os encaixes possíveis e verificar se algum deles constitui um cubo.
Essa idéia possui uma complexidade potencialmente muito alta, mas há uma forma de melhorar as coisas como mostrarei a seguir.
Considere um cubo e nomeie suas faces, como A,B,C,D,E,F por exemplo e as oriente, ou seja, faça com que seja possível dizer o que é cima,baixo, esquerda e direita para cada uma (as linhas ou colunas nesses extremos da peça chamarei de lado da peça). Uma boa dica é pensar no mesmo cubo aberto em um plano, assim como naqueles dadinhos dobráveis de papelão. Além disso declare um sentido como sendo o natural para cada um desses lados, algo como em cima escolho esquerda para direita, na direita escolho cima para baixo e etc. (esse exemplo é baseado no sentido horário)
Verifique como são as arestas desse cubo. Em outras palavras, para cada aresta verifique sua natureza, algo como a aresta é entre a parte de cima de C e a esquerda de D e as orientações desses lados dessas faces coincidem ao percorrer essa aresta ou percorro segundo uma e contra outra.
Agora construa uma rotina para comparar dois lados de peças e dizer se colidem, ou seja, que seja capaz de receber dois lados e a informação adicional de se estes devem ser comparados segundo suas orientações naturais ou invertendo a orientação de um deles. Faça de forma que ela devolva "sim" se não há colisão em nenhuma parte dos lados e se toda parte que não é uma extremidade dos lados seja preenchida por pelo menos um dos lados recebidos e não caso contrário.
Para fazer o backtracking, mantenha a sua representação de cubo fixa assim como todas as arestas que você deve verificar e varie os candidatos a substituir cada face. Ou seja para cada um entre A,B,C,D,E deve se tentar substituí-lo por todas as peças da entrada em todas as suas rotações e espelhamentos possíveis, lembrando que uma não é possível utilizar-se a mesma peça para substituir mais que uma face. Utilize a rotina proposta para verificar cada aresta e faça uma verificação adicional para cada vértice do cubo para cada uma das variações obtidas e decida se ela é ou não válida para se montar um cubo.
Para conseguir fazer que a solução rode em um tempo decente execute cada rotina assim que possível no backtracking e já elimine a variação em questão se obtiver resposta "não" para alguma delas, ou seja, vamos supor que você defina os candidatos para A,B,C,D,E e F nesta ordem, então quando definir B verifique se existir a aresta entre A e B, ao definir C, verifique as possíveis arestas entre A e C e entre B e C e assim por diante… Isso é suficiente para passar o problema com um tempo muito bom.

OBS: Qualquer coisa melhoro a análise depois. Estou viajando e me divertindo bastante =), fiz essa análise entre um passeio e outro aqui…
Talvez tenha uma ou outra entrada interessante em casa, vou ver se coloco aqui em Agosto, agora não posso.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License