Algoritmer og datastrukturer

package hjelpeklasser;

////////////////// class Labyrint //////////////////////////////

import java.io.*;
import java.util.*;
import java.net.URL;

public class Labyrint
{
  private static byte ÅPEN    = 0;
  private static byte VEGG    = 1;
  private static byte KRYSS   = 2;
  private static byte HØYRE   = 3;
  private static byte NED     = 6;
  private static byte VENSTRE = 9;
  private static byte OPP     = 12;

  public static byte[][] hentLabyrint(String url) throws IOException
  {
    BufferedReader inn =
      new BufferedReader(new InputStreamReader((new URL(url)).openStream()));

    String[] dim = inn.readLine().split(" ");  // filens første linje

    int m = Integer.parseInt(dim[0]);          // m er antall rader
    int n = Integer.parseInt(dim[1]);          // n er antall kolonner

    byte[][] a = new byte[m][n];               // oppretter tabellen

    for (int i = 0; i < m; i++)
    {
      String linje = inn.readLine();           // leser en linje
      for (int j = 0; j < n; j++)
      {
        if (linje.charAt(j) == '1') a[i][j] = 1;
      }
    }
    inn.close();
    return a;
  }

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

    if (i == iut && j == jut) return true;        // utgangen er funnet

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

    boolean funnet = false;                       // hjelpevariabel

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

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

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


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

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

    return funnet;
  }

  public static void skrivLabyrint(byte[][] a)
  {
    for (int i = 0; i < a.length; i++)
    {
      for (int j = 0; j < a[i].length; j++)
      {
        System.out.print(a[i][j]);
      }
      System.out.println();
    }
  }

  public static void tilHTML(byte[][] a, String fil) throws IOException
  {
    PrintWriter ut = new PrintWriter(fil);

    ut.println("<!DOCTYPE html PUBLIC \"-//W3C//DTD XHTML 1.0 Strict//EN\"");
    ut.println("\"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd\">");
    ut.println("<html xmlns=\"http://www.w3.org/1999/xhtml\" xml:lang=\"no\" lang=\"no\">");

    ut.println("<head>");
    ut.println("<title lang=\"no\">En labyrint</title>");
    ut.println("<meta http-equiv = \"Content-Type\" content = \"text/html;charset=iso-8859-1\" />");
    ut.println("</head>\n");

    ut.println("<style type=\"text/css\" media=\"screen\">");
    ut.println("<!--");
    ut.println("td.bg");
    ut.println("{");
    ut.println("  background-color: #b0b0b0;");
    ut.println("}\n");

    ut.println("table.labyrint");
    ut.println("{");
    ut.println("  margin-right: auto; margin-left: auto;");
    ut.println("  text-align: center;");
    ut.println("}\n");

    ut.println("table.labyrint td:first-child");
    ut.println("{");
    ut.println("  border-left: solid black 2px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("table.labyrint td:last-child ");
    ut.println("{");
    ut.println("  border-right: solid black 2px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("table.labyrint tr:first-child td");
    ut.println("{");
    ut.println("  border-right: solid black 1px;");
    ut.println("  border-top: solid black 2px;");
    ut.println("  border-bottom: solid black 1px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("table.labyrint tr:first-child td:last-child");
    ut.println("{");
    ut.println("  border-right: solid black 2px;");
    ut.println("  border-top: solid black 2px;");
    ut.println("  border-bottom: solid black 1px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("table.labyrint tr + tr td");
    ut.println("{");
    ut.println("  border-right: solid black 1px;");
    ut.println("  border-bottom: solid black 1px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("table.labyrint tr:last-child td");
    ut.println("{");
    ut.println("  border-right: solid black 1px;");
    ut.println("  border-bottom: solid black 2px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("table.labyrint tr:last-child td:last-child");
    ut.println("{");
    ut.println("  border-right: solid black 2px;");
    ut.println("  width: 20px;");
    ut.println("}\n");

    ut.println("-->");
    ut.println("</style>\n");

    ut.println("<body>");

    ut.println("<br /> <br /> \n");

    ut.println("<table class=\"labyrint\" border=\"0\" cellspacing=\"0\" cellpadding=\"0\">");

    int m = a.length;
    int n = a[0].length;

    for (int i = 0; i < m; i++)
    {
      ut.println("<tr>");
      for (int j = 0; j < n; j++)
      {
        if (a[i][j] == 1)
          ut.println(" <td class=\"bg\">&nbsp;</td>");  // del av en vegg
        else if (a[i][j] == 2)
          ut.println(" <td>×</td>");                    // del av en vei
        else
          ut.println(" <td>&nbsp;</td>");               // åpen rute
      }
      ut.println("</tr>");
    }
    ut.println("</table>");

    ut.println("</body>");
    ut.println("</html>");

    ut.close();
  }

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

    if (i == iut && j == jut)            // utgangen
    {
      if (lengde < kortest[0]) kortest[0] = lengde;  // oppdaterer
    }

    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,kortest);  // til høyre

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

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

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

    a[i][j] = 0;  // nuller ruten
  }

  public static int kortestVei(byte[][] a, int iinn, int jinn, int iut, int jut)
  {
    int m = a.length, n = a[0].length;      // m rader, n kolonner
    Queue<Integer> q = new ArrayDeque<>();  // en heltallskø
    q.offer(iinn); q.offer(jinn);           // legger inn inngangen

    while (!q.isEmpty())                    // så lenge som køen ikke er tom
    {
      int i = q.poll(); int j = q.poll();   // tar ut koordinatene
      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); q.offer(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); q.offer(j);           // legger inn koordinatene
      }

      if (j > 0 && a[i][j-1] == 0)          // til venstre
      {
        a[i][j-1] = VENSTRE;                // markerer retningen
        q.offer(i); q.offer(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); q.offer(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
  }

}  // class Labyrint