1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

Aceitam-se ideias.

Discussão em 'Programação' iniciada por computador000, 24 de Maio de 2009. (Respostas: 8; Visualizações: 705)

  1. computador000

    computador000 Power Member

    Boa tarde.

    Para um projecto que estou a fazer preciso de arranjar uma lógica que me permita sempre encontrar o . (ponto) mais próximo do caracter "e" numa tabela. A tabela é apresentada em formato .txt e é por exemplo assim:
    [​IMG]


    (embora o "e" possa estar em qualquer sítio, como no meio da tabela etc...). Antes da tabela no .txt vêm as dimensões da tabela.

    Ando às voltas com isto a ver se consigo arranjar uma relacao qualquer matemática para fazer uma espécie de "varrimento" à volta do ponto mas não chego lá. Alguém tem ideia de como se possa fazer? Obrigado.
     
    Última edição: 24 de Maio de 2009
  2. muddymind

    muddymind 1st Folding then Sex

    uma forma simples seria pegares na posição do 'e' e depois verificares circulos com raio incremental à volta da posição através de iterações.

    Seria algo do género: pegar em todas as posições com raio 1. testar uma a uma a ver se é valida (se ainda se encontra dentro da matriz) e se o for verificar se o valor é '.'

    Depois é aplicar o mesmo raciocínio para as distâncias 2, 3, 4, até que haja um raio que não tem nenhuma posição válida e aí terminas ;) (neste caso não era encontrada a solução pois a partir do momento que encontras um ponto tens a certeza q esse é um dos mais próximos e retorna-lo ;))

    []

    EDIT: Outra solução (menos boa) seria fazeres um varrimento linear à tabela e smp que encontras um ponto testas a sua distancia ao 'e' e guardas essa posiçao e a distancia numa variável. Sempre que encontras mais pontos testas se a distancia é menor q a encontrada anteriormente e caso seja usas essa. Assim vais até ao fim da tabela. Neste caso tens de percorrer obrigatoriamente toda a tabela o que torna esta solução no tipo de brute force.
     
    Última edição: 24 de Maio de 2009
  3. computador000

    computador000 Power Member

    Obrigado pelas sugestoes. Essas já sabia mas pensei que houvesse algo melhor. De qualquer forma muito obrigado
     
  4. muddymind

    muddymind 1st Folding then Sex

    Melhor que a do raio incremental acho difícil arranjar :D
     
  5. computador000

    computador000 Power Member

    Pois também não me parece que haja.

    Já agora deixo aqui outro problema para quem tiver ideias :p. Outra coisa que tenho de fazer é calcular nas tabelas fornecidas, o caminho mais curto entre o ponto 'a' na tabela(eu sei que no exemplo apresentado há 2 'a' mas só se considera um deles), e o ponto 'e'.
    Alguém tem alguma ideia de como isto possa ser feito? Obrigado mais uma vez.
     
  6. muddymind

    muddymind 1st Folding then Sex

    Exacto :) tratas a matrix como um grafo e depois é aplicar-lhe o Dijkstra em cima :P
     
  7. computador000

    computador000 Power Member

    O problema é que não sei tratar isto com grafos. Alguém tem aí alguns links ou isso que expliquem como fazer grafos? E já agora se a tabela for 1000 por 1000 ainda da pa fazer por grafos?
     
  8. Baderous

    Baderous Banido

    Tens artigos interessantes sobre Grafos nas edições 10, 12 e 16 da Revista PROGRAMAR. Tens também aqui exemplos de Grafos em C.
     

Partilhar esta Página