Oppgave 3

Resultatet blir denne veien.

Oppgave 3

  public static void main(String[] args) throws IOException
  {
    String url = "http://www.cs.hioa.no/~ulfu/appolonius/kap1/5/labyrint.txt";
    byte[][] a = hentLabyrint(url);                 // labyrinten
    a[14][11] = 1;                                  // en ny vegg
    boolean funnet = finnVei(a, 0, 0, 19, 19);      // fra inngang til utgang
    System.out.println(funnet ? "En vei er funnet!" : "Ingen vei!");
    tilHTML(a,"labyrint.html");                     // labyrinten i html-format
  }

Oppgave 6

  public static void
  finnVei(byte[][] a, int i, int j, int iut, int jut, boolean[] funnet)
  {
    a[i][j] = 2;                            // ruten er besøkt

    if (i == iut && j == jut)               // utgangen
    {
      funnet[0] = true;
      return;
    }

    int m = a.length;                       // antall rader
    int n = a[0].length;                    // antall kolonner

    if (!funnet[0] && j + 1 < n && a[i][j+1] == 0)
      finnVei(a,i,j+1,iut,jut, funnet);             // til høyre

    if (!funnet[0] && i + 1 < m && a[i+1][j] == 0)
      finnVei(a,i+1,j,iut,jut, funnet);             // nedover    

    if (!funnet[0] && j > 0 && a[i][j-1] == 0)
      finnVei(a,i,j-1,iut,jut, funnet);             // til venstre    

    if (!funnet[0] && i > 0 && a[i-1][j] == 0)
      finnVei(a,i-1,j,iut,jut, funnet);             // oppover

    if (!funnet[0]) a[i][j] = 0;                    // blindvei
  }

Metoden kan f.eks. brukes slik:

  public static void main(String[] args) throws IOException
  {
    String url = "http://www.cs.hioa.no/~ulfu/appolonius/kap1/5/labyrint.txt";
    byte[][] a = hentLabyrint(url);               // labyrinten
    boolean[] funnet = {false};
    finnVei(a, 0, 0, 19, 19, funnet);            // fra inngang til utgang
    System.out.println(funnet[0] ? "En vei er funnet" : "Ingen vei!");
    tilHTML(a,"labyrint.html");                  // labyrinten i html-format
  }

Oppgave 7

  public static boolean
  finnVei(byte[][] a, int i, int j, int iut, int jut, int lengde)
  {
    a[i][j] = 2;                            // ruten er besøkt

    if (i == iut && j == jut)               // utgangen
    {
      System.out.println("Veilengden er: " + lengde);
      return true;
    }

    int m = a.length;                       // antall rader
    int n = a[0].length;                    // antall kolonner

    boolean funnet = false;

    if (!funnet && j + 1 < n && a[i][j+1] == 0)
      funnet = finnVei(a,i,j+1,iut,jut,lengde+1);   // til høyre

    if (!funnet && i + 1 < m && a[i+1][j] == 0)
      funnet = finnVei(a,i+1,j,iut,jut,lengde+1);   // nedover    

    if (!funnet && j > 0 && a[i][j-1] == 0)
      funnet = finnVei(a,i,j-1,iut,jut,lengde+1);   // til venstre    

    if (!funnet && i > 0 && a[i-1][j] == 0)
      funnet = finnVei(a,i-1,j,iut,jut,lengde+1);   // oppover

    if (!funnet) a[i][j] = 0;                       // blindvei

    return funnet;
  }  

Oppgave 8

  public static byte[][] kopi(byte[][] a)
  {
    int m = a.length;
    byte[][] b = new byte[m][];
    for (int i = 0; i < m; i++) b[i] = a[i].clone();
    return b;
  }

  public static void finnKortestVei(byte[][] a, int i, int j,
  int iut, int jut, int lengde, int[] minimum, byte[][][] b)
  {
    a[i][j] = 2;                         // ruten er besøkt

    if (i == iut && j == jut)            // utgangen
    {
      if (lengde < minimum[0])
      {
        minimum[0] = lengde;
        b[0] = kopi(a);
      }
    }

    int m = a.length, n = a[0].length;   // m rader og n kolonner

    if (j + 1 < n && a[i][j+1] == 0)
      finnKortestVei(a,i,j+1,iut,jut,lengde+1,minimum,b);  // til høyre

    if (i + 1 < m && a[i+1][j] == 0)
      finnKortestVei(a,i+1,j,iut,jut,lengde+1,minimum,b);  // nedover

    if (j > 0 && a[i][j-1] == 0)
      finnKortestVei(a,i,j-1,iut,jut,lengde+1,minimum,b);  // til venstre

    if (i > 0 && a[i-1][j] == 0)
      finnKortestVei(a,i-1,j,iut,jut,lengde+1,minimum,b);  // oppover

    a[i][j] = 0;
  } 

Dette kan brukes slik:

  public static void main(String[] args) throws IOException
  {
    String url = "file:///e:/appolonius/kap1/5/labyrint.txt";
    byte[][] a = hentLabyrint(url);

    int[] minimum = {Integer.MAX_VALUE};
    byte[][][] b = {null};

    finnKortestVei(a, 0, 0, 19, 19, 0, minimum,b);

    if (minimum[0] == Integer.MAX_VALUE )
    {
      System.out.println("Det er ingen vei!");
    }
    else
    {
      System.out.println("Korteste vei har lengde " + minimum[0]);
      tilHTML(b[0], "labyrint.html");
    }
  }