uCoder | 1003 | Nível: 3 | Tempo Limite: 10
Vizinhança
Adaptado por erich.rodriguesf
Competição: Interfatecs 2014 1ª fase
Cinco pessoas (Alfredo, Beto, Cláudio, Darci e Ernesto) desejam comprar lotes em um terreno. Os lotes estão definidos de forma tabular como indica um exemplo de mapa da figura a baixo.
Como corretor interessado em vender os lotes, o seu problema não é convencer as pessoas a comprar os terrenos, todas se dispõem a ficar com qualquer um, desde que sejam respeitadas as diferenças pessoais que existem entre alguns. Infelizmente, as pessoas têm problemas de relacionamento e são bastante restritivas no que se refere a vizinhos. Assim, temos:
· Alfredo não quer ser vizinho de Beto, e também não quer ser vizinho de Darci;
· Beto não deve ser vizinho de Alfredo e não suportaria a vizinhança de Cláudio;
· Darci não gostaria de ter Alfredo como vizinho;
· Cláudio não quer ter Beto como vizinho;
· Ernesto não tem problemas de relacionamento com ninguém, afinal ele sempre convida todos para um samba no Brás.
Nenhum lote pode ser ocupado por mais de uma pessoa, uma pessoa pode comprar mais de um lote e uma pessoa pode ficar sem terreno. O conceito de vizinhança é definido onde um lote tem um dos lados em comum com outro lote, e não é considerado um vizinho se está na diagonal. Na figura abaixo, que mostra um mapeamento válido, o lote do Alfredo é vizinho do lote do Ernesto e de Cláudio mas não de Beto. Beto é vizinho de Ernesto mas não de Alfredo e Cláudio. Já Darci tem dois lotes e não tem vizinhos.
|
0 |
A |
E |
B |
|
0 |
C |
0 |
0 |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
D |
D |
Seu trabalho então é verificar se os mapeamentos de entrada correspondem a uma definição de vizinhança válida, ou seja, que satisfaça as restrições.
Entrada
As primeiras informações a serem lidas são o comprimento (linhas-L) e a largura (colunas-C) total do terreno onde estão os lotes a venda (0 < C e L < 1000), nesta ordem, em uma linha separados por um espaço em branco.
Nas próximas linhas são apresentados a definição dos lotes dentro do terreno a venda. As iniciais de cada nome indicam a posição de cada uma das pessoas distribuídas nos lotes. O número 0 (zero) indica que o lote está vazio.
O terreno total a venda está definido em formato de uma matriz. Onde C é o número de colunas da matriz e L é o número de linhas.
A entrada termina quando L = C = 0.
Saída
Para cada mapeamento de lotes deve ser impresso o texto “V” ou “F” (em maiúsculas e sem as aspas), onde “V” indica que o mapeamento é válido e “F” que é inválido.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
4 4 0 A E B 0 C 0 0 0 0 0 0 0 0 D D
|
V |