Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

TRAFEGO - Tráfego

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 é:

Picture of an example

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;
  5. 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.


Autor do Problema: João Paulo Fernandes Farias

Adicionado por:Wanderley Guimarăes
Data:2007-10-11
Tempo limite:0.225s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Segunda Seletiva para Maratona de Programacao UFRN - 2004

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.