URI Online Judge | 1234

O Enigma do Príncipe

Por Leandro Zatesko, UFFS BR Brazil

Timelimit: 8

Neste ano, ao invés de se submeterem a rituais de iniciação humilhantes, os calouros do curso de Ciência da Computação resolver fazer algo muito mais humanitário para celebrarem seu ingresso numa universidade federal. Primeiramente, eles foram doar sangue no HEMOSC, o hemocentro do estado de Santa Catarina. Depois, ainda com metade do sangue no corpo, eles foram até uma escola pública, o Centro de Educação Infantil Municipal Pequeno Príncipe (ou simplesmente Pequeno Príncipe), realizar trabalhos voluntários. Numa das atividades desenvolvidas, as crianças da escola deveriam jogar no computador um jogo single-player muito interessante chamado Flood It!.

Em Flood It!, é apresentado ao jogador um grid N × M em que cada célula está pintada com uma cor, como na figura à esquerda. Quando o jogador clica numa célula qualquer do grid de cor α, a célula no canto superior esquerdo do grid, chamada de origem, de cor β, assume a cor α, mas não somente ela: todas as células que estejam conectadas à origem por caminhos que usam apenas as cores α ou β também assumem a cor α. As adjacências entre as células devem ser consideradas apenas nos sentidos horizontal ou vertical para formar os caminhos. Por exemplo, quando o jogador clica na célula destacada na figura à esquerda, o grid assume a coloração da figura à direita. O objetivo do jogo é tornar o grid monocromático.

    

Entrada

A primeira linha da entrada é constituída por 2 números inteiros N e M (1 ≤ N ≤ 4, 1 ≤ M ≤ 5), os quais representam respectivamente o número de linhas e o número de colunas do grid. As próximas N linhas descrevem a configuração inicial do grid, representando cada cor por um inteiro entre 0 e 9. A entrada não é constituída por nenhuma outra linha.

Saída

Imprima uma linha contendo unicamente o inteiro que representa o menor número de cliques que o jogador precisa fazer para tornar o grid monocromático. Tome cuidado! Fomos generosos ao definirmos os casos de teste e o limite de tempo deste problema, mas nem tanto.

Exemplos de Entrada Exemplos de Saída

4 5
00162
30295
45033
01837

10

4 5
01234
12345
23456
34567

7

4 5
01234
34567
67890
90123

12