XXVI Olimpíada Brasileira de Informática
Submeta sua solução

Nome do arquivo: cor.x, onde x deve ser c, cpp, java, js ou py

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
	
Promoção
logo sbc
Patrocínio
Apoio
Coordenação