Oppgave 1

Programmet gir flg. resultat:

Korteste vei fra (0,0) til (19,19) − lengde 66

Du tar vekk veggen i rute (15,8) ved flg. tillegg i koden:

  String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap1/5/labyrint.txt";
  byte[][] a = Labyrint.hentLabyrint(url);
  a[15][8] = 0;
  int veilengde = Labyrint.kortestVei(a, 0, 0, 19, 19);
  // resten som før

Nå vil programmet gi dette resultatet:

Korteste vei fra (0,0) til (19,19) − lengde 56

Oppgave 2

Koden bli mer oversiktlig med to hjelpemetoder (de må legges inn i klassen Labyrint). De kalles i metoden kortestVei():

  public static boolean innenfor(byte[][] a, int i, int j)
  {
    return (i > 0 && i < a.length - 1 && j > 0 && j < a[0].length - 1);
  }

  public static boolean utenfor(byte[][] a, int i, int j)
  {
    return (i < 0 || i > a.length - 1 || j < 0 || j > a[0].length - 1);
  }

  public static int kortestVei(byte[][] a, int iinn, int jinn, int iut, int jut)
  {
    // sjekker om inngang og utgang ligger på kanten av labyrinten

    if (innenfor(a, iinn, jinn))
      throw  new IllegalArgumentException("Inngangen er inne i labyrinten!");

    if (utenfor(a, iinn, jinn))
      throw  new IllegalArgumentException("Inngangen er utenfor labyrinten!");

    if (innenfor(a, iut, jut))
      throw  new IllegalArgumentException("Utgangen er inne i labyrinten!");

    if (utenfor(a, iut, jut))
      throw  new IllegalArgumentException("Utgangen er utenfor labyrinten!");

    // sjekker om inngang og utgang er åpen

    if (a[iinn][jinn] != 0)
      throw  new IllegalArgumentException("Inngangen er lukket!");

    if (a[iut][jut] != 0)
      throw  new IllegalArgumentException("Utgangen er lukket!");

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

    Queue<Integer> q = new ArrayDeque<>();  // en heltallskø
    q.offer((iinn << 16) | jinn);           // de 16 første og 16 siste bitene

    while (!q.isEmpty())                    // så lenge som køen ikke er tom
    {
      int koordinater = q.poll();
      int i = koordinater >> 16, j = koordinater & ((1 << 16) - 1);
      if (i == iut && j == jut) break;      // dette er utgangen

      if (j + 1 < n && a[i][j+1] == 0)      // til høyre
      {
        a[i][j+1] = HØYRE;                  // markerer retningen
        q.offer(i << 16 | (j + 1));         // legger inn koordinatene
      }

      if (i + 1 < m && a[i+1][j] == 0)      // nedover
      {
        a[i+1][j] = NED;                    // markerer retningen
        q.offer((i + 1) << 16 | j);         // legger inn koordinatene
      }

      if (j > 0 && a[i][j-1] == 0)          // til venstre
      {
        a[i][j-1] = VENSTRE;                // markerer retningen
        q.offer(i << 16 | (j - 1));         // legger inn koordinatene
      }

      if (i > 0 && a[i-1][j] == 0)          // oppover
      {
        a[i-1][j] = OPP;                    // markerer retningen
        q.offer((i - 1) << 16 | j);         // legger inn koordinatene
      }
    }

    if (a[iut][jut] == ÅPEN) return 0;      // ingen vei til utgangen

    int i = iut, j = jut, veilengde = 0;    // starter i utgangen

    while (i != iinn || j != jinn)          // går tilbake til inngangen
    {
      veilengde++;
      int retning = a[i][j];                // retningen hit
      a[i][j] = KRYSS;                      // del av veien

      if (retning == HØYRE) j--;            // venstre er motsatt vei
      else if (retning == NED) i--;         // opp er motsatt vei
      else if (retning == VENSTRE) j++;     // høyre er motsatt vei
      else i++;                             // ned er motsatt vei
    }

    a[i][j] = KRYSS;                        // del av veien
    return veilengde;                       // lengden på veien
  }

Oppgave 3

  byte[][] a =
  {{0,1,0,0,0,0},{0,0,0,1,0,1},{1,1,0,0,0,1},{0,0,0,1,0,0}};

  int veilengde = Labyrint.kortestVei(a, 0, 0, 3, 5);
  if (veilengde < 1) System.out.println("Ingen vei!");
  else
  {
    System.out.println("Lengden på kortest vei: " + veilengde);
    Labyrint.tilHTML(a,"labyrint.html");
  }

(0,0) til (3,5) - lengde 8

Oppgave 4

  public static void
  skrivLabyrint(String filnavn, byte[][] a) throws IOException
  {
    PrintWriter ut = new PrintWriter(filnavn);
    int m = a.length, n = a[0].length;      // m rader, n kolonner

    ut.println(m + " " + n);

    for (int i = 0; i < m; i++)
    {
      for (int j = 0; j < n; j++) ut.print(a[i][j] == 1 ? 1 : 0);
      ut.println();
    }

    ut.close();
  }

Oppgave 5

  public static Graf fraLabyrint(byte[][] a)
  {
    int m = a.length, n = a[0].length;      // m rader, n kolonner
    Graf graf = new Graf();                 // en tom graf

    for (int i = 0; i < m; i++)
    {
      for (int j = 0; j < n; j++)
      {
        if (a[i][j] == 0)  // åpen rute
        {
          String node = i + "," + j;
          graf.leggInnNode(node);

          if (i - 1 >= 0 && a[i - 1][j] == 0)
          {
            String opp = (i - 1) + "," + j;
            graf.leggInnNode(opp);
            graf.leggInnKant(node, opp);
          }

          if (j + 1 < n && a[i][j + 1] == 0)
          {
            String høyre = i + "," + (j + 1);
            graf.leggInnNode(høyre);
            graf.leggInnKant(node, høyre);
          }

          if (i + 1 < m && a[i + 1][j] == 0)
          {
            String ned = (i + 1) + "," + j;
            graf.leggInnNode(ned);
            graf.leggInnKant(node, ned);
          }

          if (j - 1 >= 0 && a[i][j - 1] == 0)
          {
            String venstre = i + "," + (j - 1);
            graf.leggInnNode(venstre);
            graf.leggInnKant(node, venstre);
          }
        }
      }
    }

    return graf;
  }

  public static void main(String... args) throws IOException
  {
    String url = "https://www.cs.hioa.no/~ulfu/appolonius/kap1/5/labyrint.txt";
    byte[][] a = Labyrint.hentLabyrint(url);

    Graf g = fraLabyrint(a);  // bruker metoden over
    String fra = 0 + "," + 0;
    String til = 19 + "," + 19;
    String[] vei = g.kortestVei(fra, til);
    System.out.println("Veien har lengde "
      + (vei.length - 1) + " og går via disse rutene:");

    int linjenr = 1;
    for (String n : vei)
    {
      System.out.print("(" + n + ") ");
      linjenr++;
      if (linjenr % 10 == 0) System.out.println();
    }
  }

  Veien har lengde 66 og går via disse rutene:
  (0,0) (1,0) (2,0) (3,0) (4,0) (4,1) (4,2) (4,3) (4,4) 
  (4,5) (4,6) (4,7) (5,7) (6,7) (7,7) (8,7) (9,7) (9,8) (9,9) 
  (10,9) (11,9) (11,10) (11,11) (11,12) (11,13) (11,14) (11,15) (11,16) (11,17) 
  (12,17) (12,18) (12,19) (13,19) (14,19) (14,18) (14,17) (14,16) (14,15) (13,15) 
  (13,14) (13,13) (13,12) (13,11) (14,11) (15,11) (16,11) (17,11) (18,11) (19,11) 
  (19,12) (19,13) (18,13) (17,13) (16,13) (16,14) (16,15) (17,15) (18,15) (18,16) 
  (18,17) (17,17) (16,17) (16,18) (16,19) (17,19) (18,19) (19,19)