uCoder | 1310 | Nível: 6 | Tempo Limite: None
Linhas de Contêiners
Adaptado por Erich Rodrigues
Competição: Maratona de Programação da SBC 2013
Um carregamento de Nlogs, principal produto de exportaçãao de Nlogônia, está no porto, em contêineres, pronto para ser embarcado. Todos os contêineres têm as mesmas dimensões e são cubos. Os contêineres estão organizados no pátio do porto em L linhas e C colunas, num total de LC contêineres. Cada contêiner está marcado com um número de identificação distinto, de 1 a LC.
Cada uma das L Linhas de Contêiners será embarcada em um navio distinto. Para facilitar o desembarque nos divesos países em que serão entregues, os containeres de uma linha devem estar organizados de forma que os números de identificação estejam ordenados. Mais precisamente, a linha 1 foi organizada no pátio de forma a conter os contêineres identificados de 1 a C ordenados crescentemente, a linha 2 de forma a conter os contêineres de C + 1 a 2C (ordenados crescentemente), e assim por diante, até a linha L, organizada de forma a conter os contêineres de (L − 1)C + 1 a LC (ordenados crescentemente). A figura (a) abaixo mostra a organização de um carregamento com 5 linhas e 4 colunas de contêineres.
O guindaste de embarque é capaz de movimentar ou uma linha completa ou uma coluna completa de contêineres, não sendo capaz de movimentar outros tipos de agrupamentos ou contêineres individuais.
Na noite anterior ao embarque, um grupo de estivadores operou os guindastes para trocar linhas e colunas do carregamento, como forma de protestar quanto aos baixos salários. A figura (b) acima mostra a configuração dos contêineres após a troca das linhas 1 e 4; a figura (c)mostra a configuração após mais uma troca, entre as colunas 2 e 3.
O carregamento precisa ser embarcado ainda hoje, mas antes disso é necessário que os contêineres sejam reorganizados da forma descrita. Você deve escrever um programa que, dada a informação sobre a posição de cada contêiner após o protesto, determine se é possível recolocar os contêineres na forma originalmente prevista utilizando apenas os guindastes, e nesse caso calcular o menor número de trocas de linhas e colunas necessário para esse fim.
Entrada
A primeira linha de um programa contém dois inteiros L e C indicando respectivamente o número de linhas e o número de colunas do carregamento. As L linhas seguintes descrevem a posição dos contêineres depois do protesto dos estivadores. Cada uma dessas L linhas contém C números inteiros X l,c indicando a posição de um contêiner. Cada número inteiro entre 1 e LC aparece na entrada, em alguma das L linhas. É garantido que cada número na configuração apareça uma única vez cada e que todos os números entre 1 e LC aparecerão na mesma.
Saída
Seu programa deve produzir uma única linha, contendo um único inteiro, o número mı́nimo de trocas de linhas e colunas que devem ser realizadas pelo guindaste para recolocar os contêineres na posição original. Se não for possı́vel colocar os contêineres na posição original, utilizando apenas trocas de linhas e colunas, imprima o caractere ‘*’.
Restrições
• 1 ≤ L ≤ 300
• 1 ≤ C ≤ 300
• 1 ≤ Xl,c ≤ LC
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
5 4 |
2 |
|
3 3 |
* |
|
2 2 |
1 |