MAC323 Algoritmos e estruturas de dados II

• Estude o Web Exercise 4.1.5 (Perfect maze) de Algs4th, disponível em http://algs4.cs.princeton.edu/41undirected/.
• Altere a classe Maze.java para que ela tenha o seguinte comportamento.
  • O usuário executará seu programa dando um inteiro N na linha de comando. Alternativamente, uma semente seed para o gerador de números aleatórios também será dada na linha de comando:

    $ java-algs4 Maze N [seed]
    

    Naturalmente, o labirinto gerado pelo seu programa deve ser o mesmo quando executado com a mesma semente. Uma vez gerado, seu programa deve desenhar o labirinto em uma janela.

  • O usuário dará na entrada padrão uma seqüência de pares origem/destino. Por exemplo, poderíamos ter

    $ cat st.txt
     1  1 30 30
     1 30 30  1
     1 15 30 15
    15  1 15 30
     5 20 25 15
    15 15 17 17
    $ java-algs4 Maze 30 20150527 < st.txt 
    

    A linha 1 1 30 30 indica que queremos um caminho da posição (1, 1) à posição (30, 30). Na execução acima, seu programa deve desenhar o labirinto, e deve então resolver cada um dos 6 pares origem/destino em st.txt. Para cada par, seu programa deve desenhar a solução, da mesma forma que faz a versão original de Maze.java.

    Por exemplo, uma execução de seu programa poderia gerar o seguinte labirinto:

    

    Se o usuário der o par origem/destino (1, 1)/(60, 60), seu programa geraria a seguinte solução e figura:

    

    Para o par origem/destino (10, 55)/(45, 10), seu programa geraria a seguinte solução e figura:

    
• Importante. Seu programa deve ser tal que, para cada par origem/destino, o tempo gasto pelo seu programa é proporcional ao comprimento do caminho entre a origem e o destino. Diga por que seu programa satisfaz este requisito. (Note que, em particular, seu programa não pode fazer uma busca em largura ou uma busca em profundidade para cada par origem/destino.)
• Sugestão. Ao criar o labirinto, armazene informações adicionais (por exemplo, não seria útil ter algo como edgeTo[]?).

---

Página principal de MAC323, 1o. semestre de 2015

---