Normalmente, nos parques de estacionamento dos centros comerciais, os lugares de estacionamento estão organizados em filas paralelas, duas a duas, com uma faixa de circulação entre cada par de filas. Nos parques mais sofisticados, existe um sistema de semáforos para facilitar a localização de lugares livres pelos condutores que querem estacionar. É muito simples: coloca-se um semáforo por cima de cada lugar de estacionamento. Quando o lugar está livre, o semáforo fica verde; quando está ocupado, fica vermelho.
O parque de estacionamento do futuro TopaShopping de Loulé usará uma organização de lugares revolucionária, suprimindo as faixas de circulação. Quer dizer, a placa de estacionamento estará dividida em células de estacionamento retangulares, todas contíguas, cada uma com um semáforo. É verdade que, havendo condutores desrespeitosos, alguns carros podem ficar bloqueados, isto é, impossibilitados de sair do parque. Além disso, pode acontecer que certas zonas do parque fiquem vazias mas inacessíveis, porque há carros estacionados rodeando essa zona completamente. Para facilitar a vida aos clientes que querem estacionar, ajudando-os a encontrar lugar para o carro, vão usar-se semáforos com três cores - verde, vermelho e amarelo - funcionando da seguinte forma:
Em cada momento, cada uma das células de estacionamento estará ocupada, livre, bloqueante ou isolada. Estará ocupada, com o semáforo vermelho, se lá estiver um carro parado; estará livre, com o semáforo verde, se estiver vazia mas não bloqueante nem isolada; estará bloqueante, com o semáforo amarelo, se estiver vazia mas, se estivesse ocupada, pelo menos uma das células adjacentes que estejam ocupadas ficaria com o respetivo carro bloqueado; estará isolada, com o semáforo apagado, se estiver livre mas inacessível a partir do exterior do parque.
Note que um carro pode estar bloqueado mesmo sem estar entalado entre quatro carros (um à frente, outro atrás, outro à esquerda e outro à direita). Na verdade estar bloqueado significa que os lugares adjacentes à frente, atrás, à esquerda e à direita estão todos ocupados ou isolados.
Note ainda que, não sendo o parque de estacionamento vedado, os carros que estacionarem nas filas das pontas nunca ficarão bloqueados. Além disso, pode-se entrar na superfície do parque por qualquer uma das células de estacionamento das filas das pontas, desde que estejam vazias. Logo, essas células nunca ficarão isoladas.
| \(1\leq W\leq 100\) | Número de colunas |
| \(1\leq H \leq 100\) | Número de linhas |
8 6 0 0 1 0 3 0 4 0 5 0 6 0 2 1 5 1 6 1 2 2 4 2 5 2 6 2 1 3 2 3 3 3 5 3 7 3 3 4 6 4 0 5 2 5 5 5 7 5 -1 -1
22122221 11200223 13202223 12223202 11321121 21211212
O input corresponde à seguinte configuração, ainda sem semáforos:
Note que o sistema é prático mas não é perfeito. Quer dizer, não garante que um carro que estacione num lugar com luz verde não impeça outro carro de sair do parque. O sistema apenas assinala que um carro que estacionasse num lugar com luz amarela bloquearia pelo menos um dos carros estacionados nos lugares adjacentes.