SPOJ Brasil

HandTop Co. está desenvolvendo um novo jogo, chamado Tráfego! para sua linha de computadores de mão. Cada fase do jogo é um quebra-cabeça onde você deve conduzir um bloco para fora de uma sala que contém outros blocos. É claro que os outros blocos estão no caminho e, obviamente, nem todo movimento é possível para cada tipo de bloco. Para tornar as coisas ainda mais desafiantes, o usuário é informado do número mínimo de movimentos de modo que ele pode comparar a solução dele do quebra-cabeça com a(s) melhor(es) solução(ões) possível(is).

Um exemplo de um quebra-cabeça é:

A sala é um tabuleiro de 6 X 6, de modo que a posição no canto superior esquerdo está na coordenada (0,0) e a posição no canto inferior direito está na coordenada (5,5).

A sala pode conter 5 tipos diferentes de blocos:

1. O bloco branco é o bloco que você precisa retirar da sala, como indicado pela seta preta. Há um único bloco branco e ele somente pode se mover na horizontal;
2. Blocos verticais de tamanho 2 podem se mover somente na vertical;
3. Blocos verticais de tamanho 3 podem se mover somente na vertical;
4. Blocos horizontais de tamanho 2 podem se mover somente na horizontal;
6. Blocos horizontais de tamanho 3 podem se mover somente na horizontal.

Um movimento de bloco (na horizontal ou na vertical) deve ser completo. Por exemplo, o bloco com o número 1 possui três movimentos legais (ir 1 posição para a direita, 2 posições para a direita ou 3 posições para a direita). O bloco branco, com o número 3, não pode fazer nenhum movimento. Somente o bloco branco pode ser movido para fora da sala.

Seu objetivo é, dada uma configuração inicial, computar o número mínimo de movimentos legais para retirar o bloco branco da sala.

Entrada

A primeira linha da entrada é N, o número de quebra-cabeças para os quais você deve computar a solução, seguido por N especificações de quebra-cabeças.

Um quebra-cabeça é especificado por cinco linhas sucessivas:

1. a coordenada do bloco branco;
2. o número e as coordenadas dos blocos verticais de tamanho 2;
3. o número e as coordenadas dos blocos verticais de tamanho 3;
4. o número e as coordenadas dos blocos horizontais de tamanho 2;
5. o número e as coordenadas dos blocos horizontais de tamanho 3.

A posição de um bloco é a coordenada do quadrado superior esquerdo que ele ocupa. Uma coordenada é um par de inteiros, cada um no intervalo [0, 5], de modo que o primeiro número identifica a linha, ao passo que o segundo identifica a coluna. Portanto, o quadrado no canto superior esquerdo da tela possui coordenada (0,0), o quadrado no canto superior direito possui coordenada (0,5), o quadrado no canto inferior esquerdo possui coordenada (5,0) e o quadrado no canto inferior direito possui coordenada (5,5).

Você pode assumir que há sempre uma seqüência de movimentos que fazem o bloco branco sair da sala.

Saída

Para cada quebra-cabeça, o seu programa deve produzir uma linha indicando o número mínimo de movimentos para retirar o bloco branco.

Exemplo

A entrada a seguir corresponde ao exemplo mostrado mais acima:

Entrada:
1
2 1
1 4 0
3 1 0 1 3 0 5
2 0 0 4 4
1 5 2

Saída:
The minimal number of moves to solve puzzle 1 is 8.