uCoder | 1245 | Nível: 3 | Tempo Limite: 10
Sapos de Tsé-Tsé
Adaptado por Erich Rodrigues
Competição: IME–USP - VIII Maratona de Programação
A mosca do sono é uma das pragas mais sérias na China, que causa prejuízos enormes ao governo do país. Populações inteiras de pequenas cidades são picadas pela mosca e acabam caindo no sono durante o trabalho (muitos suspeitam que nem são as moscas as causadoras do problema, mas isso é outra história...).
Preocupados com esta situação os pesquisadores de Engenharia Genética da Universidade de Zhao-Zhao estudaram o genoma de um sapo comedor de insetos da região e descobriram que o padrão de saltos do sapo poderia ser facilmente controlado se uma alteração fosse feita em seu cromossomo 12. Infelizmente nem todos os experimentos resultaram em sucesso e, além de alguns sapos sem pernas e com 12 olhos, os experimentos deram origem a várias espécies de sapos com características diferentes de saltos. O objetivo deste problema é que vocês desenvolvam um programa que, a partir da observação do padrão de saltos de um sapo, verifique se ele é do tipo desejado. Um sapo é do tipo desejado se colocado no canto superior esquerdo de um lago retangular ele cobrir toda a extensão do lago com um número mínimo de saltos.
Para anotar o padrão de saltos de um sapo foram feitos vários experimentos. Em cada experimento o sapo foi colocado em uma posição do lago e se anotou para que posição vizinha ele saltou. As posições vizinhas são ordenadas de 1 a 8 no sentido dos ponteiros do relógio, começando na posição imediatamente acima da posição do sapo, como na figura abaixo.
Sua tarefa é dada uma instância de um lago, marcado em cada uma de suas posições com o padrão de saltos do sapo, verificar se este, quando colocado no canto superior esquerdo do lago percorre todas as suas posições.
Entrada
São dadas várias instâncias. Cada instância começa com dois inteiros 0 ≤ m ≤ 1000 e 0 ≤ n ≤ 1000 que definem a dimensão do lago. Em seguida vêm m linhas com n números inteiros, descrevendo o comportamento do sapo quando colocado naquela posição do lago. Valores m = n = 0 indicam o final das instâncias e não devem ser processados.
Saída
Para cada instância solucionada, você deverá imprimir um identificador Instancia h em que h é um número inteiro, seqüencial e crescente a partir de 1. Na linha seguinte, você deve imprimir sim se o sapo passou por todas as mn posições do lago e nao em caso contrário. Você deve imprimir uma linha em branco APÓS cada caso de teste.
| Exemplo de Entrada | Exemplo de Saída |
|---|---|
|
3 3 |
Instancia 1 |