Topas 2012 - exG

[polska]

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 August 6, 2012 at 12:11 PM by polska

[HappyHippyHippo]

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 ?

[polska]

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?

[HappyHippyHippo]

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 ...

[polska]

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 August 6, 2012 at 02:45 PM by polska

[HappyHippyHippo]

é 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 August 6, 2012 at 02:57 PM by HappyHippyHippo

[polska]

nunca tinha usado enums, vou experimentar :b, thanks

[Warrior]

Uma solução simples:

int dx[] = {1, 0, -1, 0};
int dy[] = {0, -1, 0, 1};

int direccao = 0;

Mudar de direcção é simplesmente fazer direccao = (direccao+1)%4; .

Avançar um passo é fazer x += dx[direccao], y += dy[direccao]; .