O Arranha-Céu é um jogo inspirado em cidades com enormes arranha-céus. Esse jogo tem regras simples, mas pode ser bastante desafiador. Um jogador recebe uma grade de $n \times n$ quadrados e tem como objetivo preencher todas as caixas com números de 1 a $n$. Cada número a ser preenchido representa o tamanho de um arranha-céu, ou seja, o número 1 representa um edifício de 1 andar, o 2, um edifício de dois andares e assim por diante.

A regra principal diz que dois arranha-céus com a mesma altura não podem ser colocados em uma mesma linha ou em uma mesma coluna. Além disso, ao redor de cada linha ou coluna, temos um número que corresponde a uma pista. Por exemplo, na grade abaixo de tamanho $4 \times 4$, as pistas são os números colocados nas caixas coloridas com a cor de chumbo.

Cada pista ao redor de uma linha ou coluna representa o número de edifícios que poderíamos ver nessa linha ou coluna se estivéssemos naquela posição, olhando a partir do chão. Por exemplo, à esquerda da terceira linha, temos a pista 3. Isso significa que a partir dali deve ser possível ver 3 edifícios. Uma possível maneira para preencher essa linha é construir edifícios com 2, 1, 3 e 4 andares, respectivamente.

Neste exemplo, poderiam ver a partir da esquerda apenas os edifícios com 2, 3 e 4 andares, enquanto o edifício que tem um único andar seria ocultados pelo que tem dois andares. Da mesma forma, no lado direito dessa linha temos a pista 1, que diz que daquela posição poderíamos ver apenas um arranha-céu. Isso ocorre porque o edifício de 4 andares ocultará os demais de 3, 2 e 1 andares.

Essas pistas também se aplicam às colunas. Por exemplo, na primeira coluna temos a pista 1 em cima, indicando que podemos ver apenas um edifício no sentido da seta e 2 em baixo, indicando que podemos ver dois edifícios no sentido da seta.

O quebra-cabeça proposto acima seria resolvido da seguinte forma:

Implemente um programa arranhaceu.c que resolve o quebra-cabeça do dos arranha-céus.

Entrada

A primeira linha contém o inteiro $n$ que indica o tamanho da grade ($n \times n$).

As linhas a seguir detalham o quebra-cabeça.

Exemplo de entrada

Abaixo está o exemplo de entrada para o quebra-cabeça mostrado no início.

4
0 1 2 2 3 0
1 0 0 0 0 4
3 0 0 0 0 2
3 0 0 0 0 1
2 0 0 0 0 2
0 2 1 3 2 0

Saída

A grade que resolve o quebra-cabeça deve ser impressa.

Exemplo de saída

4 3 2 1 
1 2 4 3 
2 1 3 4 
3 4 1 2 

Critérios

A solução deve implementar uma estratégia de backtracking e recursão.

Lembre-se que em um algoritmo de backtracking, queremos construir uma solução parcial considerando todos os valores para um próximo elemento da solução. Para evitar que enumeremos todas as possibilidades, queremos descartar soluções parciais inválidas.

Em um problema com várias restrições, como esse jogo, pode haver mais de uma regra para excluir soluções parciais. Não tente implementar todas essas regras de uma só vez. Primeiro implemente um algoritmo de força bruta, sem backtracking. Teste. Em seguida, considere as regras mais simples para excluir soluções parciais. Só depois, considere as regras mais complicadas.

Correção

Esta tarefa será corrigida automaticamente sempre que você realizar um git push. Depois de terminada a tarefa, deve-se utilizar o botão na interface de notas para solicitar a correção de um monitor.

Turma AB: O peso desta tarefa é 3.

← Anterior Voltar Próximo →