Problema das transformações (USACO)

From AdonaiMedrado.Pro.Br
Revision as of 09:31, 19 November 2008 by 189.105.66.30 (Talk) (New page: Tradução de Transformations da USACO (http://ace.delos.com/usacoprob2?a=pbvbeOWRbRk&S=transform). == Dificuldade Única == Um padrão quadrado tamanho NxN (1<=N<=10), composto por quad...)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search
Tradução de Transformations da USACO (http://ace.delos.com/usacoprob2?a=pbvbeOWRbRk&S=transform).

Dificuldade Única

Um padrão quadrado tamanho NxN (1<=N<=10), composto por quadrados brancos e pretos, pode ser transformado em outro padrão quadrado. Escreva um programa capaz de reconhecer a menor transformação ao qual o padrão original foi submetido dada a seguinte lista de possiveis transformações:

  • #1: Rotação de 90 graus: o padrão foi rotacionado 90 graus no sentido horário.
  • #2: Rotação de 180 graus: o padrão foi rotacionado 180 graus no sentido horário.
  • #3: Rotação de 270 graus: o padrão foi rotacionado 270 graus no sentido horário.
  • #4: Reflexão: o padrão foi refletido horizontalmente (transformado em um espelho de si mesmo a partir de uma linha vertical no meio do padrão).
  • #5: Combinação: o padrão foi refletido horizontalmente e então submetido a uma das rotações de #1 a #3.
  • #6: Sem mudanças: o padrão original não foi alterado.
  • #7: Transformação inválida: o novo padrão não foi obtido por qualquer dos métodos anteriores.

No caso de mais de uma transformação gerar o resultado, escolha como resposta aquela que tiver o menor dos valores.

Formato de entrada

  • Linha 1: Um único inteiro, N.
  • Linha 2..N+1: N linhas de N caracteres ('@' ou '-'); este é o padrão antes da transformação.
  • Linha N+2..2*N+1: N linhas de N caracteres ('@' ou '-'); este é o padrão depois da transformação.
Nome do arquivo de entrada: transform.in.

Exemplo de entrada

3
@-@
---
@@-
@-@
@--
--@

Formato de saída

Uma única linha contendo um número de 1 a 7 (conforme descrito acima) que classifica a transformação requerida para da representação "antes" se chegar à representação "depois".

Nome do arquivo de entrada: transform.out.

Exemplo de saída

1