polska Posted August 6, 2012 at 12:10 PM Report Share #471581 Posted August 6, 2012 at 12:10 PM (edited) 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 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 More sharing options...
HappyHippyHippo Posted August 6, 2012 at 01:30 PM Report Share #471587 Posted August 6, 2012 at 01:30 PM 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 Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 6, 2012 at 02:23 PM Author Report Share #471594 Posted August 6, 2012 at 02:23 PM 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 More sharing options...
HappyHippyHippo Posted August 6, 2012 at 02:28 PM Report Share #471595 Posted August 6, 2012 at 02:28 PM 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 Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 6, 2012 at 02:43 PM Author Report Share #471597 Posted August 6, 2012 at 02:43 PM (edited) 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 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 More sharing options...
HappyHippyHippo Posted August 6, 2012 at 02:56 PM Report Share #471598 Posted August 6, 2012 at 02:56 PM (edited) é 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 IRC : sim, é algo que ainda existe >> #p@p Portugol Plus Link to comment Share on other sites More sharing options...
polska Posted August 6, 2012 at 03:36 PM Author Report Share #471599 Posted August 6, 2012 at 03:36 PM nunca tinha usado enums, vou experimentar :b, thanks 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 More sharing options...
Warrior Posted August 6, 2012 at 03:44 PM Report Share #471600 Posted August 6, 2012 at 03:44 PM 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]; . Link to comment Share on other sites More sharing options...
Recommended Posts
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 accountSign in
Already have an account? Sign in here.
Sign In Now