Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 5 de Junho
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #09]

[DAA 032] Quadrados mágicos
(este problema é uma adaptação de um problema das IOI'1996)

Depois do sucesso do cubo mágico, o Sr. Rubik resolveu inventar uma versão "planar", a que chamou de quadrados mágicos. Essencialmente é constituído por um tabuleiro com 8 quadrados iguais, cada um com uma cor diferente:

1 2 3 4
8 7 6 5
Configuração Inicial

Neste problema identificamos cada cor por um número inteiro entre 1 e 8. Uma configuração do tabuleiro é dada pela cores começando no canto superior esquerdo e continuando no sentido dos ponteiros do relógio. Por exemplo, a configuração inicial (na figura de cima) é dada pela sequência (1,2,3,4,5,6,7,8).

Existem três transformações básicas que podemos aplicar a um tabuleiro, identificadas pelas letras 'A', 'B' e 'C':

A figura seguinte ilustra o estado do tabuleiro depois de aplicada cada uma das três transformações ao tabuleiro inicial:

A:  
8 7 6 5
1 2 3 4
  B:  
4 1 2 3
5 8 7 6
  C:  
1 7 2 4
8 6 3 5

Usando apenas estes 3 tipos de transformações, qualquer posição é atingível num máximo de 22 movimentos (onde um movimento corresponde a uma transformação básica).

O Problema

Dada uma qualquer configuração alvo, a tua tarefa é calcular qual o menor número de movimentos que transforma a configuração inicial nessa configuração alvo. Para além disso deves indicar qual a sequência de movimentos a efectuar para fazer essa transformação.

Input

O input é constituído por uma linha contendo 8 inteiros, com a descrição da configuração alvo.

Output

Na primeira linha deve vir um único inteiro indicando o menor número de movimentos para transformar a configuração inicial na configuração alvo.

Na segunda linha deve vir um conjunto de letras identificando a sequência mínima de movimentos (transformações básica) calculada. Caso existam várias sequências mínimas, deve indicar a menor alfabeticamente.

Exemplo de Input 1

4 8 1 3 6 2 7 5

Exemplo de Output 1

2
BC

Explicação do Input/Output 1

Bastam 2 transformações básicas: B seguida de C

1 2 3 4
8 7 6 5
 → B:
4 1 2 3
5 8 7 6
 → C:
4 8 1 3
5 7 2 6

Exemplo de Input 2

8 3 2 5 4 7 6 1

Exemplo de Output 2

3
ACC

Explicação do Input/Output 2

Bastam 3 transformações básicas: A, seguida de C, seguida de C.

1 2 3 4
8 7 6 5
 → A:
8 7 6 5
1 2 3 4
 → C:
8 2 7 5
1 3 6 4
 → C:
8 3 2 5
1 6 7 4

 

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto