Oppgavesett 10 - Påskelabyrinten

Oppgavene blir tema på øvingen fredag 13. april. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment10-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment09.

Fristen for innlevering er tirsdag 10.april 09:00.

Oppgave 1: Labyrint

Ta utgangspunkt i labyrintkoden Maze.java fra forelesningen.

A

Modifiser koden slik at den for hver løsning skriver ut alle stegene i riktig rekkefølge.

B

Gjør nødvendige endringer i koden, og kjør metoden som finner alle veiene i labyrinter av økende størrelse (2x2, 2x3, 3x3, 3x4, 4x4, etc), og der både start og mål er (0, 0). Bruk dette til å lage et plott der antall veier er verdiene på y-aksen, og labyrintstørrelsen er verdiene på x-aksen.

*C

Implementer en metode void prettyPrint(), som skriver ut en løsning, der man tydelig ser rekkefølgen av stegene. Dokumenter at den virker.

D

Modifiser videre koden slik at den finner korteste vei gjennom en labyrint ved å sammenlikne alle de genererte løsningene. Dokumenter at den virker ved å kjøre den på et passende eksempel (minimum 10x10).

*E

Å finne korteste vei kan gjøres mer effektivt ved å hele tiden holde rede på lengden av den hittil korteste veien, og stoppe nye søk hvis de overskrider denne lengden. Forklar hvordan dette kan gjøres. Implementer deretter metoden, og bruk den til å utforske hvor effektiv denne avskjæringen er i praksis.