Jump to content

Topas 2012 - exG


polska

Recommended Posts

Boas pessoal, bem, estava a tentar acabar todos os exercícios do topas deste ano, mas, deparei-me com o último, e apesar de compreender o que é pedido, não o consigo resolver, achei interessante pedir ajuda neste problema pois já me tinha deparado com problemas semelhantes que também não consegui resolver...

Visto que não dá para inscrever no servidor do topas deste ano, vou tentar resumir a explicação do problema..

Basicamente temos um mapa como input:

14 23

XXXXXXXXXXXXXXXXXXXXXXX

X X X

X X B X

X B X S

X XB X

X XXXXXXXPXXXXX

X X X

X B X B B X

X XXXXXXXXXPXXX

X X X X

X P P X

X B X B X BX

X X X X

XXEXXXXXXXXXXXXXXXXXXXX

O objectivo do problema é sabermos quantos balões podemos apanhar junto á parede, e se ficamos presos ou não no edificio. Para isso temos um robo, que começa na célula 0 2 ('E', a contar de baixo para cima). Sempre que entra numa sala, começa a percorrer a parede para a direita, e verifica quantos balões encontra encostados á parede, no exemplo acima, ele entra na primeira sala e não encontra nenhum.. Depois de completar a volta toda na sala, vai para a sala seguinte pela porta ('P'), e percorre a seguinte sala toda.. O programa acaba quando ele encontra uma sala que contém a porta de saída('S'), ou quando encontra uma sala que não contém nenhuma porta que dê para outra sala diferente..

Se encontrar a saída, o output seria:

número de balões

Levantou voo

Caso contrário:

número de balões

Veio para ficar

No exemplo acima:

4 ( um balão na terceira sala, dois na quarta sala e um na última sala)

Levantou voo

O problema é fácil de perceber e chega-se facilmente a compreender o output, mas não consigo fazer o código, o que eu pensei foi guardar numa matriz o mapa e fazer uma simulação do robô a percorre lo, o problema é que á salas em que andar para a direita significa andar para a direita nas colunas matriz, noutras significa andar para baixo, e isso estraga logo o meu raciocínio.. Já me deparei com problemas semelhantes onde devia seguir um mapa para saber a solução, mas tive o mesmo problema que neste, as direcções a percorrer na matriz e assim.. Alguém me pode dar uma ajuda? Qual seria a solução apropriada para este problema?

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

isso é a solução de descobrir o caminho para fora do labirinto, tens de trabalhar com a direção do movimento

o teu algoritmo será algo deste gênero :

- direciona o robô para dentro da sala (isto é, se X = 0 então estás virado para N, se X = Max então será para S, etc ..)
- entras num ciclo de percorrer as salas (podes usar uma função recursiva aqui)
 - andas uma posição para a frente (isto porque a tua posição é entre paredes)
 - verificas se apanhaste um balão
 - guarda a posição inicial da sala
 - ciclo até voltares novamente à posição inicial
   - verifica se pode virar à direita
   - se sim
     - vira para a direita
     - guardas a direção tomada (N/S/E/O)
   - se não
     - é porta ?
     - se sim
       - guardas a posição da porta
     - verifica se pode ir para a frente
     - se sim
       - andas uma posição para a frente
     - se não
       - é porta ?
       - se sim
         - guardas a posição da porta
       - verificas se podes andar para a esquerda
       - se sim
         - vira para a direita
         - guardas a direção tomada (N/S/E/O)
       - se não
         - (agora é complicado e provavelmente não deverás contemplar este caso porque envolve andar para trás e tomares outro caminho)
 - verifica se descobriste uma porta
 - se sim
   - vai para a posição da porta
   - soma o resultado da chamada recursiva ao número de balões que apanhaste nesta sala
   - retorna o resultado da soma
 - se não
   - retorna o número de balões apanhados

o truque é : tens sempre de trabalhar com a direção do último passo para saber que lado é a direita, frente e esquerda

agora, pode haver pequenas variações :

- pode existir mais que uma porta por sala ?

- pode existir uma saída numa sala com uma porta para uma sala diferente ?

- existe alguma sala com beco sem saída que envolve voltar para trás ?

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

agora, pode haver pequenas variações :

- existe alguma sala com beco sem saída que envolve voltar para trás ?

Se for beco sem saida, acaba o programa, não sai dessa sala. Se encontrar sala com 'S', acaba também, são as duas condições de paragens do programa.

Desculpa, não percebi como sei que estou virado para sul, norte... Podes explicar melhor sff?

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

Se for beco sem saida, acaba o programa, não sai dessa sala. Se encontrar sala com 'S', acaba também, são as duas condições de paragens do programa.

eu quando falei num beco sem saída é numa sala deste gênero:

 XXX
XXX XXX
X     X
X     P
XXPXXXX

como podes ver, ao percorrer a parede superior, tens de entrar num beco sem saída que te faz andar para tráz

Desculpa, não percebi como sei que estou virado para sul, norte... Podes explicar melhor sff?

imagina que tens uma seta que indica o robô e a sua direção

// estou virado para este
XXXXXXX
X     X
X   > P
XXPXXXX

// estou virado para sul
XXXXXXX
Xv    X
X     P
XXPXXXX

// estou virado para oeste
XXXXXXX
X  <  X
X     P
XXPXXXX

// estou virado para norte
XXXXXXX
X    AX
X     P
XXPXXXX

só sabendo para onde estás virado, podes descobrir que sentido é direita, frente e esquerda, se é norte, sul, este ou oeste ...

IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

eu quando falei num beco sem saída é numa sala deste gênero:

XXX
XXX XXX
X X
X P
XXPXXXX

como podes ver, ao percorrer a parede superior, tens de entrar num beco sem saída que te faz andar para tráz

Ah! 😄 , entendi mal xb

imagina que tens uma seta que indica o robô e a sua direção

// estou virado para este
XXXXXXX
X X
X > P
XXPXXXX

// estou virado para sul
XXXXXXX
Xv X
X P
XXPXXXX

// estou virado para oeste
XXXXXXX
X < X
X P
XXPXXXX

// estou virado para norte
XXXXXXX
X AX
X P
XXPXXXX

só sabendo para onde estás virado, podes descobrir que sentido é direita, frente e esquerda, se é norte, sul, este ou oeste ...

Já entendi, uma var auxiliar que me indique para onde estou virado, e faço os movimentos consoante o que me indica a variavel.

4 bools não? um norte, sul, este, oeste..

Edited by polska

Corrige um sábio e ele mais sábio ficará. Corrige um ignorante e um inimigo ganharás.

Link to comment
Share on other sites

é mais simples usares um enum

typedef enum 
{
 Norte,
 Sul,
 Este,
 Oeste
} Dir;

int main()
{
 Dir direcao = Norte;

 switch (direcao)
 {
   case Norte:
     break;
   case Sul:
     break;
   case Este:
     break;
   case Oeste:
     break;
 }

 return 0;
}
Edited by HappyHippyHippo
IRC : sim, é algo que ainda existe >> #p@p
Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.