XXVI Olimpíada Brasileira de Informática
Lápis de Cor
Roberto tem um conjunto de lápis com 10 tons diferentes de uma mesma cor, numerados de 0 a 9. Numa folha de caderno quadriculado alguns quadrados foram coloridos inicialmente com o tom 0. Roberto precisa determinar, para cada quadrado Q não colorido, qual é a distância dele para o quadrado mais próximo de tom 0. A distância entre dois quadrados é definida com o número mínimo de movimentos ortogonais (para: \it esquerda, direita, cima, baixo) para ir de um quadrado para o outro. O quadrado Q, então, deve ser colorido com o tom cuja numeração corresponde à distância determinada. Se a distância for maior ou igual a 9, o quadrado deve ser colorido com o tom 9. Seu programa deve colorir e imprimir a folha quadriculada dada na entrada.
Entrada
A primeira linha da entrada contém apenas um inteiro N, determinando as dimensões da folha quadriculada, Nx N. As N linhas seguintes definem a folha inicialmente. Cada linha contém uma sequência de N caracteres: `*" se o quadrado não está colorido, e `0" se está colorido com o tom 0.Saída
Seu programa deve imprimir o tabuleiro totalmente colorido, de acordo com a regra definida acima.Restrições
- 3 ≤ N ≤ 1000.
Informações sobre a pontuação
- Em um conjunto de casos de teste somando 40 pontos, N ≤ 100
Exemplos
Entrada
8 **000*** ******** *****0** ******** *****000 *******0 0******0 ******** |
Saída
21000123 32111123 43221012 34332111 23321000 12332110 01233210 12344321 |
Entrada
3 *** *** **0 |
Saída
432 321 210 |
