SPOJ Brasil

Número de Flechas é um quebra-cabeça. O objetivo é determinar as orientações das flechas posicionadas no perímetro de um tabuleiro quadrado em forma de grade. As pistas do quebra-cabeça são dadas como inteiros escritos dentro de cada quadrado do tabuleiro: cada inteiro indica quantas flechas apontam para aquele quadrado. Flechas podem apontar apenas para uma das oito direções da bússola e sempre devem apontar para pelo menos um quadrado do tabuleiro.

Escreva um programa que, dado um tabuleiro de Número de Flechas, encontra uma solução válida ou diz que não existe solução. A Figura 1 exibe um exemplo que possui solução.

Entrada

A entrada contém vários tabuleiros. A primeira linha da descrição de um tabuleiro contém um único inteiro N indicando o tamanho do tabuleiro. Cada uma das próximas N linhas contém N inteiros, separados por espaços, correspondendo aos números escritos nos quadrados do tabuleiro.

Há uma linha em branco após cada descrição de tabuleiro.

A entrada termina com uma linha contendo 0 (N = 0). Esta linha não deve ser processada.

Restrições

1 <= N <= 8
Cada número do tabuleiro possui valor entre 0 e 8 (inclusive).

Saída

Para cada tabuleiro, a primeira linha da saída deve ser "Instancia #I:", onde I é o índice do tabuleiro na entrada, começando de 1.

Se o tabuleiro não tem solução, a próxima linha da saída deve ser sem solucao. Se o tabuleiro tem uma solução, as próximas N + 2 linhas da saída devem descrever a solução (todas as instâncias terão solução única). A saída deve ser formatada como uma grade (N + 2) x (N + 2). Cada célula da grade deve ter espaço para dois caracteres, alinhamento a direita e as células são separadas por espaços.

As N x N células centrais devem conter os números do tabuleiro original. As 4N células da borda devem conter as orientações das flechas, impressas como direções da bússola exibidas na Figura 2. Os quatro cantos devem conter apenas espaços em branco (em particular, a primeira e a última linha da saída devem conter espaços em branco no início e no final).

Há uma linha em branco após cada saída.

Exemplo de entrada

3
5 2 5
3 0 1
4 3 4

2
0 0
0 0

4
4 3 3 0
7 3 3 2
5 3 3 2
3 1 3 0

0

Saída para o exemplo de entrada

Instancia #1:
    S SE  S   
 E  5  2  5  W
NE  3  0  1 NW
 E  4  3  4  W
    N NE NW   

Instancia #2:
sem solucao

Instancia #3:
    S SW SW SW   
SE  4  3  3  0 SW
NE  7  3  3  2  W
NE  5  3  3  2  W
NE  3  1  3  0 NW
    N NW  N NW